问题 D: Power Strings(Poj2406)

问题 D: Power Strings(Poj2406)

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 10
[提交][状态][讨论版][命题人:add_cst][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1717&pid=3

题目描述

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).

输入

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.

输出

For each s you should print the largest n such that s = a^n for some string a.

样例输入

abcd

aaaa

ababab

.

样例输出

1

4

3

思路：说那么长，其实难点就是在求整个字符串的最大匹配长度。

因为最大匹配长度是前缀等于后缀，所以向后遍历【原式长度-最大匹配长度】一定会发生重复。

So，答案就是原式长度/(原式长度-最大匹配长度)。

代码：

#include<bits/stdc++.h>

using namespace std;

int Next[1000000];

void get_next(string child)

{

    memset(Next, 0, sizeof(Next));

    int i = 0;

    int j = -1;

    Next[0] = -1;

    while (i < child.length())

    {

         if (j == -1 || child[i] == child[j])

         {

             ++i;

             ++j;

             Next[i] = j;

         }

         else

         {

             j = Next[j];

         }

    }

}

int main()

{

    string child;

    while (cin >> child && child[0] != '.')

    {

         memset(Next, 0, sizeof(Next));

         get_next(child);

         int n = child.length();

         if(n % (n - Next[n])==0)

         cout << n / (n - Next[n]) << endl;//原式长度/(原式长度-最大匹配长度)

         else cout << 1 << endl;

    }

}