題目意思：
給你一個串r,求一個串s,使得s的前綴1+s的前綴2+s的前綴3+...+s的前綴n+s=r .
解題思路：
KMP+貪心。
初始時把r[1]賦給s[1],從r中每個字符從前至後依次匹配s,當匹配失敗時，說明該字符在模式串中沒有出現，由貪心思想，把它放到最後（前面滿足要求的話，最短的也要從上個完全匹配開始），所以把從上一次的完全匹配的位置到該字符之間的所有字符作為新的模式串，繼續匹配。
當完全匹配時，更新上次完全匹配的位置值。
代碼：
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
#define M 100005
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
char rr[M],pp[M];
int rn,pn,next[M];
void getnext(int s)
{
int j=next[s-1];//只需從上一個開始計算
//int j=s-1;
for(int i=s;i<=pn;i++)
{
while(j>0&&pp[j+1]-pp[i])
j=next[j];
if(pp[j+1]==pp[i])
j++;
next[i]=j;
}
return ;
}
int main()
{
int ca=0;
while(scanf("%s",rr+1)!=EOF)
{
rn=strlen(rr+1);
pp[1]=rr[1];
pn=1;
next[1]=0;
int last=1;//記錄上一個完全匹配的位置
int j=0;
for(int i=1;i<=rn;i++)
{
while(j>0&&pp[j+1]-rr[i])
j=next[j];
if(pp[j+1]==rr[i])
j++;
if(j==pn) //找到了新的完全匹配
{
last=i-pn+1;
j=next[j];//往回跳一個
}
else if(j==0) //有新的字母，只能作為最後一個
{
int tmp=pn;
for(int k=last+pn;k<=i;k++)
pp[++pn]=rr[k];
getnext(tmp+1); //不是getnext(last+tmp) last是隨i增加的，wa了一上午
//j=pn;
}
}
printf("Case %d: %d\n",++ca,rn-last+1);
}
return 0;
}
</SPAN>
