点击打开链接poj2406
思路:kmp+最小循环节
分析:
1 题目要求的是给定一个字符串找到最小循环节的个数,但是这里有个限制的地方就是如果这个字符串不是刚好由n个最小循环节组成那么就认为一整串才是一个循环节
2 题目说了输入的字符是可打印的,所以应该用gets读入,判断终止的时候用strcmp。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; #define MAXN 1000010 char pattern[MAXN]; int next[MAXN]; void getNext(){ int m = strlen(pattern); next[0] = next[1] = 0; for(int i = 1 ; i < m ; i++){ int j = next[i]; while(j && pattern[i] != pattern[j]) j = next[j]; next[i+1] = pattern[i] == pattern[j] ? j+1 : 0; } int cir = m-next[m]; if(m%cir == 0)/*刚好由n个最小循环节组成*/ printf("%d\n" , m/cir); else/*否则都是输出1*/ printf("1\n"); } int main(){ while(gets(pattern)){ if(!strcmp(pattern , ".")) break; getNext(); } return 0; }
时间: 2024-08-01 18:32:23