HDU3746 Teacher YYF 题解 KMP算法

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3746

题目大意：给你一个串 \(s\) ，要求 \(s\) 的开头或结尾添加最少的字符，使得添加后的串可以表示为 \(K\) 个相同的子串的拼接 \(（K>=2）\) 。

题目分析：首先如果这个串s已经是一个循环串了，这种情况下 \(nxt[m-1] != -1\) 且 \(m-1-nxt[m-1]\) 能够整除 \(m\) ，那么输出 \(0\) 即可。

错误分析： 不然的话，我们添加一些字符后的串应该是 \(m-1-nxt[m-1]\) 长度的两倍，所以要添加的字符的数量是 \((m-1-nxt[m-1)*2-m\) 。（这样是WA的）。

然后，我们令 \(len = m-1-nxt[m-1]\) ，答案就是 \(len - m % len\) 。

实现代码如下：

#include <string>

#include <iostream>

#include <cstdio>

using namespace std;

const int maxn = 100100;

int T, m, nxt[maxn];

string t;

char ch[maxn];

string read() {

    scanf("%s", ch);

    string tmp_s = ch;

    return tmp_s;

}

void cal_next() {

    m = t.length();

    for (int i = 0, j = -1; i < m; i ++) {

        while (j != -1 && t[j+1] != t[i]) j = nxt[j];

        nxt[i] = (j+1 < i && t[j+1] == t[i]) ? ++j : -1;

    }

}

int main() {

    scanf("%d", &T);

    while (T --) {

        t = read();

        cal_next();

        int p = nxt[m-1] + 1;

        if (nxt[m-1] != -1 && m % (m-1-nxt[m-1]) == 0) {

            puts("0");

        } else {

            // printf("%d\n", (m-1-nxt[m-1])*2-m );

            int len = m-1-nxt[m-1];

            printf("%d\n", len - m % len );

        }

    }

    return 0;

}

作者：zifeiy