POJ 2406

蔚落 2022-08-21 11:58 17阅读 0赞

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

找最小循环节

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char a[1000005];
    int nxt[1000005];
    int cnt;
    void get_nxt()
    {
    	int i=0;
    	int j=-1;
    	nxt[0]=-1;
    	int l=strlen(a);
    	while(i<l)
    	{
    		if(j==-1||a[i]==a[j])
    		{
    			i++;
    			j++;
    			nxt[i]=j;
    		}
    		else
    			j=nxt[j];
    	} 
    }
    int main()
    {
    	int i,j,k,m,n,l;
    	while(~scanf("%s",a),a[0]!='.')
    	{
    			int f=0;
    			memset(nxt,0,sizeof(nxt));
    			int l1=strlen(a);	
    			get_nxt();
    			i=l1; 
    			int t=i-nxt[i];
    		 	if(i!=t&&i%t==0)
    			{
    				f=1;
    				printf("%d\n",l1/t);
    			}
    			if(f==0)
    			printf("1\n");
    
    		
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2406

Description Given two strings a and b we define a\b to be their concatenation. For exam

蔚落/ 2022年08月21日 11:58/ 0 赞/ 18 阅读

相关 poj 2406 Power Strings【kmp】

Power Strings Description Given two strings a and b we define a\b to be their concaten

电玩女神/ 2022年08月21日 02:17/ 0 赞/ 28 阅读

相关 POJ 2406 Power Strings（KMP+最小循环节）

Given two strings a and b we define a\b to be their concatenation. For example, if a = "

电玩女神/ 2022年06月10日 14:08/ 0 赞/ 196 阅读

相关 POJ 2406 Power Strings(Next数组的应用)

[传送门][Link 1] 题意：给你一个字符串，要求输出该字符串的最小循环节的个数，但是这里需要注意一个地方，如果这个字符串不是刚好由n个最小循环节组成那么就认为这整个字符

女爷i/ 2022年05月19日 07:06/ 0 赞/ 199 阅读

相关 KMP-(POJ 2406)Power Strings[字符串乘方]

KMP-(POJ 2406)Power Strings\[字符串乘方\] -------------------- 题目链接：[Power Strings

ゞ浴缸里的玫瑰/ 2022年05月17日 08:51/ 0 赞/ 162 阅读

相关 POJ 2406 Power Strings——————KMP next数组的利用

Power Strings <table> <tbody> <tr> <td> <div> Language:Default

灰太狼/ 2022年05月16日 09:15/ 0 赞/ 166 阅读

相关 kmp2-HDU1358 HUST1010 POJ2406 POJ2752

HDU1358 [http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showprob

Dear 丶/ 2022年05月14日 11:25/ 0 赞/ 153 阅读

相关 poj2406

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] /\Poj2406题解： if (len % (len \

た入场券/ 2021年12月22日 10:07/ 0 赞/ 166 阅读

相关 poj(2406)(kmp)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 // kmp算法 2 \include " io

小咪咪/ 2021年12月22日 09:45/ 0 赞/ 225 阅读

相关 poj-2406 Power Strings

<table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS</td> <td>

绝地灬酷狼/ 2021年11月01日 04:26/ 0 赞/ 240 阅读