HUST - 1010 The Minimum Length（最小循环节）

1、赤裸裸的最小循环节

2、

3、

#include

#include

#include

using namespace std;

#define MAXN 1000005//字符串长度

int _next[MAXN];

void GetNext(char t[]){//求next数组

int j,k,len;

j=0;//从0开始，首先求_next[1]

k=-1;//比较指针

_next[0]=-1;//初始值-1

len=strlen(t);

while(j

if(k==-1||t[j]==t[k]){//指针到头了，或者相等

++j;

++k;

_next[j]=k;//此句可由优化替代

/*优化（求匹配位置时可用）

if(t[j]!=t[k])_next[j]=k;

else _next[j]=_next[k];

//*/

}

else k=_next[k];

}

}

int main(){

char str[MAXN];

int len,len2;

while(~scanf("%s",str)){

len=strlen(str);

GetNext(str);//求子串的next数组

len2=len-_next[len];//最小循环节

printf("%d\n",len2);

}

return 0;

}

好文阅读