【bzoj1355】 Baltic2009

题意 给定一个字符串A，求最短的字符串B，使得A是若干个B连接成的字符串的前缀 若A=abcabcab 则B=abc

求出A串在KMP算法中A的next数组 设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]; }