问题 E: Radio Transmission(Bzoj1355)

问题 E: Radio Transmission(Bzoj1355)

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

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

题目描述

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

输入

第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.

输出

请输出最短的长度

样例输入

8

cabcabca

样例输出

3

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

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

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

代码：

#include<bits/stdc++.h>

using namespace std;

int Next[1000000];

void get_next(string child)//求Next[]数组

{

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

{

    int n;

    cin >> n;

    string child;

    cin >> child;

    get_next(child);

    cout << child.length() - Next[child.length()];

}