Power Strings

发表于 更新于 分类于

Problem’s Website

  • Power Strings

    Solution

  • 根据kmp算法，一个字符串循环节的长度为len-next[len]，不懂的可以自行模拟一下，那么对于这道题来说，如果有循环节，那么len-next[len] | len，这样我们就可以A掉这道题。

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define Maxn 1000010
    using namespace std;
    char s[Maxn];
    int next[Maxn];
    int main() {
    	while(1) {
    		scanf("%s", s + 1);
    		int len = strlen(s + 1);
    		if(len == 1 && s[1] == '.') break;
    		memset(next, 0,sizeof(next));
    		int j = 0;
    		for(int i = 2; i <= len; i++) {
    			if(j > 0 && s[j + 1] != s[i])
    				j = next[j];
    			if(s[j + 1] == s[i])
    				j++;
    			next[i] = j;
    		}	
    		if(!(len % (len - next[len])))
    			printf("%d\n", len / (len - next[len]));
    		else
    			printf("1\n");
    	}
    	return 0;
    }

rp++