HUST 1010-The Minimum Length-KMP

╰半夏微凉° 2022-08-09 17:58 2阅读 0赞

The Minimum Length

**Time Limit:**1000MS **Memory Limit:**131072KB **64bit IO Format:**%lld & %llu

Submit [Status][]

Description

There is a string A. The length of A is less than 1,000,000. I rewrite it again and again. Then I got a new string: AAAAAA...... Now I cut it from two different position and get a new string B. Then, give you the string B, can you tell me the length of the shortest possible string A. For example, A="abcdefg". I got abcd **efgabcdefgabcde**fgabcdefg.... Then I cut the red part: efgabcdefgabcde as string B. From B, you should find out the shortest A.

Input

Multiply Test Cases. For each line there is a string B which contains only lowercase and uppercase charactors. The length of B is no more than 1,000,000.

Output

For each line, output an integer, as described above.

Sample Input

bcabcab
    efgabcdefgabcde

Sample Output

3
    7

有一个字符串，长度小于1000000。我一遍又一遍的重写。然后我有了一个新的字符串：aaaaaa ......现在我把它从两个不同的位置，得到一个新的字符串，然后，给你的字符串B，你能告诉我，例如最短的字符串的长度，A="abcdefg". I got abcd**efgabcdefgabcde**fgabcdefg....…然后我把红色部分：efgabcdefgabcde作为字符串B，你应该找出最短的A.  
  
多试验例。每一行有一个字符串B只包含小写和大写。长度不超过1000000。

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int maxt=1000000+10;
    char t[maxt];
    int next[maxt];
    int main()
    {
        while(scanf("%s",t)!=EOF)
        {
            int p=0,cur,l;
            next[0]=-1;
            next[1]=0;
            l=strlen(t);
            for(cur=2; cur<=l; ++cur)
            {
                while(p>=0&&t[p]!=t[cur-1])
                    p=next[p];
                next[cur]=++p;
            }
            printf("%d\n",l-next[l]);
        }
        return 0;
    }

KMP模板题，调用求子模板串的模式值next\[n\]，再用串的长度减去next\[n\]即得到答案。

[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=97614#status//A/0