子串循环问题 (Ver. I)

目录

题目描述

思路分析

AC代码

---

题目描述

给定一个字符串，求需要添加至少几个字符到字符串末尾才能使得整个字符串串由某一个不为本身的子串循环构成？
如"abca"，添加"bc"后构成"abcabc"，其由子串"abc"循环构成;也可以添加"abca"后构成"abcaabca"，其由子串"abca"循环构成，相比之下"bc"只有2个字符，添加的字符量最少。

输入

第一行包括一个整数T(1 <= T <= 100)，代表测试组数

每组测试数据包括一行字符串，其长度范围为 [3, 10^4]

输出

对于每组测试数据

输出一个整数N，代表添加的最小字符数量

输入样例1

3
aaa
abca
abcdefg

输出样例1

0
2
7

思路分析

利用到KMP的next值。

我课上学的是下标从1开始的，next【0】存的是子串的长度，下一个next值需要根据前一个next值来确定，首先判断当前字符的前面所组成的字符串的前后缀（前一个字符和第一个字符）是否是相同的字符，如果相同，那么当前字符的next值为前一个next值+1，如果不同，继续比较前一个字符和前一个next值所对应的字符是否相同，如果都不相同，那么next值为1。

这里需要用到一个定理：

定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]。

这里的next值是从下标0开始的，我们可以让下标从1开始的next值减1来来表示。

令L=len - next[len]，那么满足题目的数值是L-next[len]%L。

AC代码

#include 
 
using namespace std;
 
int FindNext(string son) {
	son+='#';
    int next[son.size() + 1];
    next[0] = son.size();
    next[1] = 0;
    int i = 2, j = 0;
    while (i <= next[0]) {
        if (j == 0 || son[i - 2] == son[j - 1]) {
            next[i] = j + 1;
            i++;
            j = next[i - 1];
        } else j = next[j];
    }
    size_t len=son.size()-1;
    size_t L=len-next[son.size()]+1;
    if(len%L==0&&len/L>1)
    return 0;
    return L-(next[son.size()]-1)%L;
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        string test;
        cin >> test;
        cout<<FindNext(test)<
    }
}