【KMP】洛谷 P2375 动物园

题链

暴力想法就是求前缀数组，然后倒着一步步得跳$j$指针直到长度小于当前总长一半，最后把$j$指针跳到$0$的次数总和就是答案，当然会$T$，例如全是’$a$’

在求前缀数组时可以递推记录当前长度有多少个相同前后缀的个数，此时不管前后缀区间是否重叠

用与求前缀数组同样的想法去跳指针$j$，每次都得出不超过长度一半的最长前后缀的长度$j$，不更新$j$的值就能保证每次$j$值都在$i/2$的左边

为何第$0$个字符要等于$1$，$ac$数组记录的相同前后缀个数而不是真前后缀个数

因为在跳$j$指针的时候，当$j$长度小于当前总长一半时，$ans$若乘上真前后缀个数，则会少一个当前$s[0…j-1]$这个本体..

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define mod 1000000007
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9

LL n,m,k;
char s[MS];
LL kp[MS];
LL ac[MS];

int main(){
	ios::sync_with_stdio(false);
	cin >> k;
	while(k--){
		cin >> s; // 字符串以0开始 
		LL hs = strlen(s);
		kp[0] = 0;
		ac[0] = 1;
		for(int i=1,j=0;i<hs;i++){
			while(j>0 && s[i] != s[j]) j = kp[j-1];
			if(s[i] == s[j]) j++; // 前两步得出以 i 为结尾匹配的最长真前后缀的长度 j 
			kp[i] = j; // 记录这个长度 j 
			if(j) ac[i] = ac[j-1]+1; // ac[i]表示以 i 结尾 相同的前后缀的个数
			else ac[i] = 1; 
		} 
		LL ans = 1;
		for(int i=1,j=0;i<hs;i++){
			while(j>0 && s[i] != s[j]) j = kp[j-1];
			if(s[i] == s[j]) j++;
			while(2*j>i+1) j = kp[j-1]; // 得出不超过长度一半的最长前后缀的长度 j  
			if(j) ans *= (ac[j-1]+1);
			ans %= mod;
		}
		cout << ans << endl;
	}

	return 0;
}