Power Strings

布满荆棘的人生 2022-12-21 06:29 90阅读 0赞

## 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).  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70_pic_center]

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  
.  
Output  
1  
4  
3  
Hint  
This problem has huge input, use scanf instead of cin to avoid time limit exceed.

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    char a[100010000];//本题测试数据很多，数组记得开大点
    int next[10001000];
    void getnext(int len)
    {
        
        int i=0,j=-1;
        next[0]=-1;
        while(i<len)
        {
        
            if(j==-1||a[j]==a[i])
            {
        
                j++;
                i++;
                next[i]=j;
            }
            else
                j=-1;
        }
    }
    int main()
    {
        
        while(~scanf("%s",a))
        {
        
            if(a[0]=='.')
            break;
            else
            {
        
                int len=strlen(a);
                memset(next,0,sizeof(next));
                getnext(len);
                int n=len-next[len];
                if(n!=len&&len%n==0)
                    printf("%d\n",len/n);
                else
                    printf("1\n");
            }
        }
    }

*利用KMP算法，求字符串的特征向量next，若len可以被len - next\[len\]整除，则最大循环次数n为len/(len - next\[len\])，否则为1。*

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/f6d776daeb2c472a8fb5e47a4c3ebf6c.png