HUST 1010 The Minimum Length（KMP）

落日映苍穹つ 2022-06-10 14:00 113阅读 0赞

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

题解：

题意：

给你一个由串A组成的串B

串B为AAAAAAAAAA去掉一些东西

问你原来的A最短是多长

思路：

在组成B还没删数之前，可以发现B串无论从任意一个位置开始都是循环的，删了一些字符，那么自身还是存在循环的部分，那么这个问题就转化为了对B串求最小的循环节了

直接KMP搞搞，目前HUST已经炸了2个星期了现在还没好我也不知道我这份代码对不对。。。

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int Next[1000005];
    char T[1000005];
    void init()
    {
        int i,j;
        i=0,j=-1;
        Next[0]=-1;
        while(T[i])
        {
            if(j==-1||T[i]==T[j])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else
                j=Next[j];
    
        }
    }
    int main()
    {
        int i,j,n;
        while(scanf("%s",&T)!=EOF)
        {
            init();
            printf("%d\n",strlen(T)-Next[strlen(T)]);
        }
        return 0;
    }