正題

評(píng)測(cè)記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2375

---

題目大意

對(duì)于kmp操作，我們多求一個(gè)numnum數(shù)組，表示對(duì)于字符串SS的前ii個(gè)字符構(gòu)成的子串，既是它的后綴同時(shí)又是它的前綴，并且該后綴與該前綴不重疊。

---

解題思路

我們可以在求next的時(shí)候進(jìn)行遞推，然后就可以求出可以重合的num。
然后我們?cè)谟胣ext去掉不可以的答案。
但是如果這樣我們就會(huì)超時(shí)，所以我們發(fā)現(xiàn)如果不重合，那么長(zhǎng)度最大為n÷2n÷2，所以我們直接不更新jj，因?yàn)檫@個(gè)位置滿足長(zhǎng)度為ii，那么也一定滿足長(zhǎng)度為i+1i+1的情況。

---

code

#include<cstdio> #include<cstring> #define mod 1000000007 using namespace std; char s[1000011]; int l,p[1000011],ans[1000001],tot,t; void ycl()//求next數(shù)組 {ans[0]=0;ans[1]=1;for (int i=1,j=0;i<l;i++){while (j&&s[i]!=s[j]) j=p[j];if (s[i]==s[j]) j++;ans[i+1]=ans[j]+1;//遞推p[i+1]=j;} } long long answer() {long long sum=1;for (int i=1,j=0;i<l;i++){while (j&&s[i]!=s[j]) j=p[j];if (s[i]==s[j]) j++;while((j<<1)>(i+1)) j=p[j];//計(jì)算j位置sum=(sum*(long long)(ans[j]+1))%mod;}return sum; } int main() {scanf("%d",&t);for(int i=1;i<=t;i++){memset(p,0,sizeof(p));scanf("%s",s);l=strlen(s);ycl();printf("%lld\n",answer());} }

總結(jié)

以上是生活随笔為你收集整理的P2375-[NOI2014]动物园【KMP,字符串】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。