KMP-(POJ 2406)Power Strings[字符串乘方]-蒲公英云

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

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

题目链接：Power Strings
思路：最小循环节

看到乘方，很明显是求给定字符串由它的最小循环子串循环得到的次数

那就是求出NEXT数组，再而求出最小循环节长度：Len-NEXT[Len]

有三种情况，分两类

①给定字符串循环子串是其本身：乘方等于1

a.NEXT[Len]=0 栗如：abcd

b.NEXT[Len]!=0,but Len%(Len-NEXT[Len]) != 0：所求循环节长度与字符串长度不成倍数，例如abbbabb，求得的可能最小循环节为abbb，很明显不是真正的循环子串，真正的最小循环节应为本身：abbbabb

②子串为最小循环节

c.Len%(Len-NEXT[Len])=0，那么循环次数也就是乘方为 Len/(Len-NEXT[Len])

题目基础：KMP-NEXT数组的性质

KMP算法-求NEXT数组：串的模式匹配算法-KMP算法

最小循环节：KMP-(HDU1358)Period[前缀中的周期]

代码：
include
include
using namespace std;
//KMP POJ 2406

define MAX_Length 1000005
int Next[MAX_Length];
int len;
char Str[MAX_Length];

void KMP()
{
    int j = -1, k = 0;
    Next[0] = -1;
    while (k < len)
    {
        if (j == -1 || Str[j] == Str[k])
        {
            j++;
            k++;
            Next[k] = j;
        }
        else
            j = Next[j];
    }
}
int main()
{
    while (cin >> Str && Str[0] != '.')
    {
        len = strlen(Str);
        KMP();
        int Min_Period_Len = len - Next[len];        //求出最小循环节长度
        if (Min_Period_Len == len || len % Min_Period_Len)        //循环节是本身的情况，那么乘方是1
            cout << "1" << endl;
        else
        {
            int Period_Num = len / Min_Period_Len;        //求出循环次数
            cout << Period_Num << endl;
        }
    }
    return 0;
}