题目分析

本题主要考察kmp中next数组在求循环时的运用：

字符串是循环的： len % (len - next[len]) == 0
字符串循环次数： len / (len - next[len])
字符串循环节长度： len - next[len]

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<ctime>

using namespace std;

const int N = 1000100;

char s[N];

int next[N], lS, ans;

inline void getNext(){

	for(int i = 2, j = 0; i <= lS; i++){

		while(j && s[i] != s[j + 1]) j = next[j];

		if(s[i] == s[j + 1]) j++;

		next[i] = j;

	}

}

int main(){

	while(~scanf("%s", s + 1), s[1] != '.'){

		memset(next, 0, sizeof next);

		lS = strlen(s + 1);

		getNext();

		if(lS % (lS - next[lS]) == 0)

			ans = lS / (lS - next[lS]);

		else ans = 1;

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

【poj2406】next数组求循环节

题目分析

code

最新文章

热门文章