傳送門

KMP好題啊……

題中要求我們求出長度不超過原字符串一般的相同的前后綴的個數。其實這個用做前面幾道題的思路大致猜測一下……可以發現，我們只要從這個字符串一直往它的next遞歸，那么我們就可以獲得一系列的公共前后綴，而且只要當next的長度<=原長度的一半的時候答案即合法。（不能繼續遞歸，否則就重復計算了）

每個點可以獲取的相同的前后綴個數可以通過kmp預處理出來，我們只要讓ans[i] = ans[j]+1,(其中next[i] = j)，因為在i向j跳的時候相當于獲取了一個長度為j的公共前后綴的貢獻。

不過我們如果這樣一直遞歸，遇到無良數據（比如200000個a），你就T飛了，因為每次遞歸只會減少1的長度。解決的方法是，我們在計算的時候也像KMP一樣，每次不更新j的位置，使之一直呆在小于i的一半的位置（因為你肯定是要小于i的一半才合法），這樣可以避免許多無用的遞歸，就可以在線性時間之內求解了。

看一下代碼。

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar('\n')using namespace std; typedef long long ll; const int M = 10005; const int N = 1000005; const ll mod = 1000000007;int read() {int ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op; }int n,nxt[N],len; char s[N]; ll cur,ans[N];void getnext() {int j = 0;rep(i,2,len){while(j && s[j+1] != s[i]) j = nxt[j];if(s[j+1] == s[i]) j++;nxt[i] = j,ans[i] = ans[j] + 1;} }void clear() {memset(nxt,0,sizeof(nxt));memset(ans,0,sizeof(ans));cur = 1; }int main() {n = read();while(n--){clear();scanf("%s",s+1),len = strlen(s+1);ans[1] = 1,getnext();int j = 0;//rep(i,0,len-1) printf("%d ",nxt[i]);enter;//rep(i,0,len-1) printf("%lld ",ans[i]);enter;rep(i,2,len){while(j && s[i] != s[j+1]) j = nxt[j];if(s[j+1] == s[i]) j++;while(j << 1 > i) j = nxt[j];// printf("!%d\n",j);cur *= (ans[j] + 1),cur %= mod;}printf("%lld\n",cur);}return 0; }

?

轉載于:https://www.cnblogs.com/captain1/p/9770007.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的NOI2014 动物园的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。