⭐⭐⭐⭐⭐【KMP & 最小循环节】Power Strings

题目描述

知识点

KMP算法以及最小循环节定理

实现

码前思考

1. KMP算法分为两个部分：
   ① 获取next数组；
   ② 进行匹配
2. 最小循环节定理：
   ① 得到理想中的最小循环节长度mod = (len-1) - next[len-1]，例如对于ababa的理想mod = 4 - 2 = 2;
   ② 使用len%mod进行判断，如果len%mod==0，那么最小循环节长度就是mod，否则最小循环节长度就是len了。输出结果就OK。

代码实现

#include <cstdio>
#include <cstring>
const int maxn = 1e6+10;

//nex数组 
int nex[maxn];

//输入字符串 
char s[maxn]; 

void getNex(){
	int len = strlen(s);
	//初始化
	nex[0] = -1;
	int j = -1;
	for(int i=1;i<len;i++){
		while(j!=-1 && s[i]!=s[j+1]){
			j=nex[j];
		}
		if(s[i] == s[j+1]){
			j++;
		}
		nex[i] = j; 
	} 
}

int main(){
	while(scanf("%s",s) && s[0] != '.'){
		//首先是getNex
		getNex();
		
		int len = strlen(s);
		
		//得到最小循环节
		int mod = len-1 - nex[len-1];
		
		if(len%mod==0){
			printf("%d\n",len/mod);
		}else{
			printf("1\n");
		}
		
	}  
	return 0;
} 

码后反思

1. 可以使用while(scanf("%s",s) && s[0]!='.')将两个操作写成一行；
2. 有些OJ会将next作为关键字，所以不要用next作为数组名，会出现问题的；
3. 需要记忆最小循环节定理，要背下来才是。。。