欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

KMP之Power Strings

程序员文章站 2022-04-24 14:06:07
...

NEFU 2131 字符串乘方

模拟过程:
这道题十分巧妙地运用了next数组的性质;
s[0...next[i]]=s[inext[i]+1...i]s[0...next[i]]=s[i-next[i]+1...i]

若s字符串存在重复,则如图所示
KMP之Power Strings
next数组的构建:

  1. next[i]next[i]数组就是描述:最长当前1i1-i长度的字符串的最长前缀和后缀的长度。
  2. 如果存在重复单元,则lennext[len]len-next[len]就是最短的循环串。
  3. lenmod  (lennext[len])=0len\mod(len-next[len])=0的话,就会存在循环节。则len/(lennext[len])len/(len-next[len])就是答案。

举例:

字符串:    a b c a b c a b c
next数组:  0 0 0 1 2 3 4 5 6

字符串:    a b c d a b c e
next数组:  0 0 0 0 1 2 3 0

字符串:    a a a a a a a b
next数组:  0 1 2 3 4 5 6 0

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int maxn = 1e6 + 5;
char s[maxn];
int Next[maxn];
int main()
{
    while (~scanf("%s", s))
    {
        if (s[0] == '.')
            break;
        int len = strlen(s);
        memset(Next, 0, sizeof(Next));
        int i = 0, j = -1;
        Next[0] = -1;   //s[i]代表后缀,s[j]代表前缀
        while (i < len) //next定义为最长的前缀==后缀
        {
            if (j == -1 || s[i] == s[j])
            {
                i++;
                j++;
                Next[i] = j;
            }
            else
                j = Next[j];
        }                                           
        if (len % (len - Next[len]) == 0)            //如果第i-1位为结尾的循环必定有 i % (i - Next[i]) == 0
            printf("%d\n", len / (len - Next[len])); //0~i-1共有i个字符,i / (i - Next[i])就是循环次数。
        else
            printf("1\n");
    }
    return 0;
}
相关标签: 题库