题目描述

Lx同学前一段时间正在学数据结构中的字符串内容，年纪轻轻的他就被里面的算法折磨的苦不堪言，什么匹配思想，什么最大前后缀，搞的是一头雾水。终于在经过好几个晚上的奋斗后终于是初步理解了字符串匹配算法的精妙之处。
Lx在学完字符串匹配算法问题后，知道了如何求出字符串的最大前后缀长度数组，于是他希望求出一个更强大数组num——对于字符串s的前i个字符构成的子串p，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。例如s为aaaaa，则num[4]=2。这是因为s的前4个字符为aaaa，其中a和aa都满足性质”既是后缀又是前缀”，同时保证这个后缀与这个前缀不重叠,而aaa虽然满足性质”既是后缀又是前缀”，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，num[1] = 0,num[2] = num[3] = 1，num[5]=2。 但是写代码时他又被自己难倒了，怎么也写不出来，那么聪明的你能解决这个问题嘛？

为了避免大量的输出，你不需要输出num[i]分别是多少，你只需要输出所有num[i]+1的积对1e9+7取模。

数据范围
对所有测试数据，字符串长度均小于100000，并且全部为小写字母。

输入
第1行仅包含一个正整数n ，表示测试数据的组数。
随后n行，每行描述一组测试数据。每组测试数据仅含有一个字符串s，s的定义详见题目描述。数据保证s 中仅含小写字母。输入文件中不会包含多余的空

输出
包含 n 行，每行描述一组测试数据的答案，对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案的积。

输入样例

3
aaaaa
abab
abcababc

输出样例

36
4
32

算法（KMP）

解题思想

Kmp中基础概念、匹配和next[]，建议先看这篇文章（再来看题）： https://www.acwing.com/solution/content/79021/

本题是KMP的进一步理解，精髓在于掌握Kmp以及递推转递归的思想，实现将朴素求法的时间复杂度$O(n^2)$转化为时间时间复杂度O(n)
①首先在进行num[i]求解前，我们先观察下next[i],可以发现，next[i]表示s[1, i]的一个前后缀，那么如何表示s[1,i]所有的前后缀嫩？因此可以得到如下性质：
对于s[1,i]:next[i],next[next[i]],next[next[next[i]…表示s[1,i]所有的公共前后缀
②接下来构造num数组，num[i]表示当前子串i中满足前缀等于后缀的个数（包含前缀i本身，和前缀后缀重叠），因此在进>行next[i]求解过程中，可以利用num[i] = num[j] + 1(其中num[j]求的是s[1,i]中前缀等于后缀的数量，加1代表的为前缀i本身)
③题目要求的是子串i中前缀等于后缀中不重叠的个数，因此j(模板串)的长度要满足j <= i / 2, 不满足时模板串恢复到上一个操作next[j],重新匹配
④最后的输出的为num[j]就是当前s[1, i]中的前缀等于后缀中不重叠的个数(不包括本身)

注意：①本题中的模板串和模式串相同
② num[0] = 0
③ num[1] = 1(理解前缀1本身)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n;
char s[N];  // 输入字符串
int ne[N];  // 部分匹配表 
int num[N];  // 保存的当前子串的中的前缀等于后缀数目(包含重叠)

int main(){
    cin >> n;

    while (n --){
        memset(num, 0, sizeof num);  // 重置
        memset(ne, 0, sizeof ne);  // 重置

        cin >> s + 1;
        int len = strlen(s + 1);

        num[0] = 0;
        num[1] = 1;
        // 求解s部分next[]
        for (int i = 2, j = 0; i <= len; i ++){
            while(j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) j ++;
            ne[i] = j;

            num[i] = num[j] + 1;  // 存储当前串的前缀等于后缀数
        }

        long long cnt = 1;  // 统计满足条件前后缀数目
        // 匹配
        for (int i = 1, j = 0; i <= len; i ++){
            while(j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) j ++;

            while(j * 2 > i) j = ne[j];  // 保证模板串中匹配成功的长度不能超过当前模式串的一半

            cnt = cnt * (num[j] + 1) % mod;
        }
        cout << cnt << endl;
    }

    return 0;
}