吶吶吶題面

這題可以說是kmp的簡化版，也就是說只用求一下next數組，答案輸出為n-next[n]，那么為什么呢，其實這也很好想，next[i]存儲的是下標為i的前綴與從頭開始最長的相同前綴的尾下標，故next[n]表示的也就是除去第一個循環節之外的其他長度

#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<cmath> #include<ctime> #include<vector> #include<bitset> #include<memory> #include<utility> #include<cstdio> #include<sstream> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int N=1000005;int n; char s[N]; int next[N];void getnext(){for(int i=2,j=0;i<=n;i++){while(s[i]!=s[j+1]&&j){j=next[j];}if(s[i]==s[j+1]){j++;}next[i]=j;} }int main(){scanf("%d",&n);cin>>(s+1);getnext();printf("%d\n",n-next[n]);return 0; }

　　我還是得抽時間整理一下kmp完整版和簡化版的區別，有點略混。。

轉載于:https://www.cnblogs.com/hahaha2124652975/p/11146673.html

總結

以上是生活随笔為你收集整理的P4391 [BOI2009]Radio Transmission 无线传输的全部內容，希望文章能夠幫你解決所遇到的問題。

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