首页 > 代码库 > POJ - 2406 Power Strings (KMP循环节)
POJ - 2406 Power Strings (KMP循环节)
Description
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
Input
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Output
For each s you should print the largest n such that s = a^n for some string a.
Sample Input
abcd aaaa ababab .
Sample Output
1 4 3 题意:题目要求的是给定一个字符串找到最小循环节的个数,但是这里有个限制的地方就是如果这个字符串不是刚好由n个最小循环节组成那么就认为一整串才是一个循环节思路:KMP应用#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int 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 len = m - next[m]; if (m % len == 0) printf("%d\n", m/len); else printf("1\n"); } int main() { while (gets(pattern)) { if (strcmp(pattern, ".") == 0) break; getNext(); } return 0; }
POJ - 2406 Power Strings (KMP循环节)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。