首页 > 代码库 > poj 2406 Power Strings(KMP&思维)
poj 2406 Power Strings(KMP&思维)
Power Strings
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 Hint This problem has huge input, use scanf instead of cin to avoid time limit exceed. Source Waterloo local 2002.07.01 |
题意:
定义a^n为aaaaa...aaa。a为一个字符串。现在给你一个字符串问你把它写成a^n的形式。就你求出最大的n。
思路:
kmp水题。关键是思维。需要对KMP有一定认识。画个图就明白了。
用自己和自己匹配。一次失配后会形成上图的状态。剪头所指的位置都是相同的。因为自己和自己匹配嘛。所以只需要判断凸出去的长度能不能整除整个串的长度就行了。不行再往前移。行的话答案就是突出去的长度了。
详细见代码:
#include <iostream> #include<stdio.h> #include<string.h> using namespace std; const int maxn=1000100; int f[maxn]; char txt[maxn]; void getf(char *p) { int i,j,m=strlen(p); f[0]=f[1]=0; for(i=1;i<m;i++) { j=f[i]; while(j&&p[i]!=p[j]) j=f[j]; f[i+1]=p[i]==p[j]?j+1:0; } } int main() { int len,i,ans,t; while(~scanf("%s",txt)) { if(txt[0]=='.') break; getf(txt); len=strlen(txt); i=len; ans=len-f[i]; while(f[i]) { t=len-f[i]; if(len%t==0) { ans=len/t; break; } i=f[i]; } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。