題意 給定一個字符串A，求最短的字符串B，使得A是若干個B連接成的字符串的前綴 若A=abcabcab 則B=abc
求出A串在KMP算法中A的next數(shù)組 設(shè)A的長度為N 則答案為A的前N-next[N]位 分兩種情況討論： next[N] > N/2 next[N] <= N/2
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;char w[1000005];int n,len_s,len_w,ans,t[1000005];inline void calc_w(){ int j; t[0]=-1; for (int i=0;i<n;i++) { j=t[i]; while(w[i]!=w[j]&j!=-1) j=t[j]; t[i+1]=++j; }}int main(){ cin>>n; scanf("%s",w); calc_w(); for (int i=1;i<=n;i++) cout<<t[i]<<' '; cout<<endl; cout<<n-t[n];}新聞熱點
疑難解答
