HUST 1010 The Minimum Length(最小循环节)

** 题目链接 ** : [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher F - The Minimum Length

题意

有一个字符串A,假设是”abcdefg”,由A可以重复组成AAA,即”abcdefgabcdefgabcdefg”,从中截取一部分(至少包含一个以上完整
A)为B。
现给出字符串B,求A最短的长度。

思路

因为是重复组成的,所以abcd==bcda==cdab==dabc,即
直接对字符串B进行最短循环节求解,循环节的长度即为A的最短长度。
ps:此题有一大易wrong点,我整整wrong了10多次,改到哭,甚至坚信是系统出问题。
今再看,尝试了用gets输入,竟然成功。
改回用scanf,加上对str的清零操作,也成功。
基本可以确定是\0惹的祸,查了下发现
gets函数会读入截止字符\n, 同时将\n自动替换为\0.
scanf遇到截止字符时不会继续读取,截止字符将存储于输入缓冲中。
因为没有\0,所以无法获取正确的字符串长度,所以wrong。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

char a[1000009];
int p[1000009];

void init(int m)
{
    memset(p, 0, sizeof(p));
    for(int i=1, k=0; i<m; i++)
    {
        while(k>0 && a[i]!=a[k]) k = p[k-1];
        if(a[i] == a[k]) k++;
        p[i] = k;
    }
}

void solve(int n)
{
    init(n);
    printf("%d\n", n-p[n-1]);
}

int main()
{
    while(~scanf("%s", a))
    {
        solve(strlen(a));
        memset(a, 0, sizeof(a));
    }
    return 0;
}