對(duì)于字符串\(S\)的前\(i\)個(gè)字符構(gòu)成的子串，既是它的后綴又是它的前綴的字符串中，它本身除外，最長(zhǎng)的長(zhǎng)度記作 \(next[i]\)
真是精煉的定義

char s[maxn];int n; int fail[maxn]; char t[maxn];int m; int fnd[maxn];void getfail(){fail[1]=0;for(int i=2,j=0;i<=n;i++){while(j && s[i]!=s[j+1])j=f[j];if(s[j+1]==s[i])j++;f[i]=j;} } int find(){for(int i=1,j=0;i<=m;i++){while(j && (j==n || s[i]!=s[j+1]))j=fail[j];if(t[i]==s[j+1])j++;fnd[i]=j;} }

具體做法參考了這里

轉(zhuǎn)載于:https://www.cnblogs.com/Drenight/p/9291067.html

總結(jié)

以上是生活随笔為你收集整理的【NOI2014】动物园 kmp性质的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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