[KMP]hdoj 3746:Cyclic Nacklace
大体の意味:
文字列を指定します.最低何文字を追加するかを求めて、この文字列を繰り返し列にします.
大体の考え: KMPの最小カバー部分列の小さい変形、最小カバー部分列の長さはlen-(next[len-1]~~具体的には参照してください. http://blog.csdn.net/fjsd155/article/details/6866991 また、poj 2185もこのような問題です.
文字列を指定します.最低何文字を追加するかを求めて、この文字列を繰り返し列にします.
大体の考え: KMPの最小カバー部分列の小さい変形、最小カバー部分列の長さはlen-(next[len-1]~~具体的には参照してください. http://blog.csdn.net/fjsd155/article/details/6866991 また、poj 2185もこのような問題です.
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax= 100005;
const int mMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){ //pat[j] i next
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
int main(){
int t,a,b;
scanf("%d",&t);
while(t--){
scanf("%s",pat);
lenp=strlen(pat);
get_next();
a=next[lenp-1]+1;
a=lenp-a; //
b=lenp%a;
if(b){
printf("%d
",a-b);
}
else{
if(a==lenp){
printf("%d
",lenp);
}
else{
printf("0
");
}
}
}
return 0;
}