题意 给定一个字符串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];}新闻热点
疑难解答
