持续更新
D-Period
预处理next数组，然后再预处理的
值不为0的数量（使用差分数组记录一下）。预处理时间复杂度
,询问
查询
总时间复杂度
代码如下
#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
const int MAXN = 1e6+7;
char str[MAXN];
int nxt[MAXN];
int n;
int cnt;
int res[MAXN];
int cf[MAXN];//差分数组
void getNext(){
nxt[1] = 0;
int j = 0;
for(int i=1;i<=n;i++){
while(j >= 1 && str[j] != str[i]){
j = nxt[j-1];
}
if(str[j] == str[i]) j++;
nxt[i] = j;
}
return;
}
void preNext(){
int j=n;
while(j > 0){
cf[nxt[j]] += 1;
j = nxt[j]-1;
}
cf[0] = 0;
for(int i=1;i<=n;i++){
cf[i] += cf[i-1];
}
}
int q;
signed main(void){
scanf("%s",str);
n = strlen(str)-1;
getNext();
preNext();
scanf("%lld",&q);
int x;
while(q--){
scanf("%lld",&x);
x = min(x-1,n-x+1);
printf("%lld",cf[x]);
if(q) printf("\n");
}
return 0;
}
