我们规定对一个字符串的shift操作如下:略去。shift(string, x) = string(0 <= x < n).

分析:一看这题,这不很简单么,直接模拟判断,但是这套路有这么简单么!看数据范围,1e6,那么复杂度就是1e6*1e6=1e12,这样,在1s的时限内,肯定会超时,暴力肯定不行,那就字符串哈希,很早就想写了,但是没有遇到专门的这类题,刚好这道题就练习一下,我忘了那个算法叫什么名字,好像是Rabin-Karp,反正就是对这个字符串算出一个值,然后可以O(1)的转移到下一个字符串,计算出下一个字符串的值,如果这两个值不相等,那么这两个字符串肯定不同,如果相等,那相同的概率就很高,这里需要再次逐个字符判断一下是否相等。这道题,我为了简单起见,就没有再次判断,已经ac。

 /*
ID: y1197771
PROG: test
LANG: C++
*/
#include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef unsigned long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e3 + ;
const int key = ;
int work(char x) {
if(x >= 'A' && x <= 'Z')
return x - 'A';
return + x - 'a';
}
void solve() {
string s, d;
cin >> s;
d = s;
int res = ;
int n = s.size();
ll t = , tag = , tar = ;
for (int i = ; i < n; i++) {
t = t * key + work(s[i]);
tag *= key;
}
tar = t;
for (int i = ; i < n - ; i++) {
t = t * key - tag * work(s[i]) + work(s[i]);
if(t == tar) res++;
}
cout << res << endl; }
int main() {
freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
solve();
return ;
}
04-27 05:34