KMP算法
KMP算法是一種字符串匹配算法，用于匹配模式串P在文本串S中出現的所有位置。
例如S=“ababac，P=“aba”，那么出現的所有位置是13。
在初學KMP時，我們只需要記住和學會使用模板即可，對其原理只需簡單理解，不要過度深究，避免把自己繞進去，可以課后自己慢慢去畫圖理解。
KMP算法將原本O（n2）的字符串匹配算法優化到了O（n）.其精髓在于next數組，next數組表示此時模式串下標失配時應該移動到的位置，也表示最長的相同真前后綴的長度。
例如P=“ababac”，S=“abababac”。
當匹配到i=6，j=5，P［i+1］！=S［i］時，j不會移動到1重新開始匹配，而是移動到nex［j］=3繼續匹配，
則接下來i=6，j=3，有P［j+1］=S［i］，成功匹配，則i，j繼續后移，直到i=8.j=6完成一次匹配，則P在S中第一次出現的位置為j-i+1=3。
計算next數組（next數組僅與模式串P有關）的方式就是用P自己去匹配自己，大家只需要掌握模板即可，暫時不要深究其原理。
char s[N],p[N];
int nex[M];
int n = strlen(s+1),m=strlen(p+1);//字符串下標從 1 開始
nex[0]=nex[1]=0;
for(int i=2,j=0;i<=m;++i){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;//從 while 出來后要么 j=0，要么 p[i]==p[j+1]，如果匹配成果，則 j 后移nex[i]=j;//如果匹配失敗就回到 j，因為此時 p[1~j]=p[i-j+1~j]或 j=0（回到最初的地方開始匹配）
}
通過 next 數組匹配
for(int i=1,j=0;i<=n;i++)
{while(j&&s[i]!=p[j+1])j=nex[j];if(s[i]==p[j+1])j++;if(j==m)//成功匹配一次
}
斤斤計較的小Z
思路：KMP 算法模板，不知道為啥結果不對
#include<bits/stdc++.h>
using namespace std;
const int N =20,M=20;
char s[N],p[M];
int nex[M];int main(){scanf("%s\n%s",p+1,s+1);int n=strlen(s+1),m=strlen(p+1);nex[0]=nex[1]=0;for(int i=2,j=0;i<=m;i++){while(j&&p[j+1]!=p[i])j=nex[j];if(p[j+1]==p[i])j++;nex[i]=j;}int res=0;for(int i=1,j=0;i<=n;i++){while(j&&p[j+1]!=s[i])j=nex[j];if(p[j+1]==s[i])j++;if(j==m)res++;}cout<<res<<'\n';return 0;
}
boarder
思路：利用 KMP 求整個串的最長真前后綴，len-nex[len]就是整個串的循環節，len 能整除循環節就是答案，不能就是 1。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char p[N];
int nex[N];
int main( ){scanf("%s",p+1);unsigned long m=strlen(p+1);nex[0]=nex[1]=0;for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;nex[i]=j;}int len=m-nex[m];if(m%len==0){cout<<m/len<<endl;}else{cout<<1<<endl;}return 0;
}幸運字符串
思路：求 nex 數組，找最大值就是答案
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n;
char p[N];
int nex[N];
int main( ){cin>>n;scanf("%s",p+1);unsigned long m=strlen(p+1);for(int i=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=nex[j];if(p[i]==p[j+1])j++;nex[i]=j;}int ans=0;for(int i=1;i<=m;i++)ans=max(ans,nex[i]);cout<<ans<<endl;return 0;
}
你也喜歡幸運字符串嗎？
思路：動態規劃+KMP，不會。
#include <bits/stdc++.h>
#define ll long long
#define PI 3.1415926
using namespace std;
typedef pair<int, int> vt;
typedef pair<vt, vt> PII;
const int N = 1e6 + 10;
const int M = 2 * N;
const int mod = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;int ne[N];
string s;
int n;void solve()
{cin >> n;cin >> s;memset(ne, 0, sizeof ne);s = " " + s;for (int i = 2, j = 0; i <= n; i++){while (j && s[i] != s[j + 1])j = ne[j];if (s[i] == s[j + 1])j++;ne[i] = j;}vector<ll> f(n + 5);for (int i = 1; i <= n; i++)f[i] = 1;for (int i = n; i >= 1; i--)f[ne[i]] += f[i];ll ans = 0;// for(int i=1;i<=n;i++)cout<<f[i]<<endl;for (int i = 1; i <= n; i++){if (ne[i] != 0)ans += f[ne[i]];}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);/*多組案例初始化*/// int t;cin>>t;while(t--)solve();
}
)
)
