回顾KMP到底干了件什么事情

计算next数组：
next数组的定义是到$i$这个点最长的与前缀相等的后缀，也就是计算公共子序列的时候再当前这个位置失配后往前跳会跳到的位置。
更普遍的一个版本是Z函数，能把字符串接起来匹配。

E. A Trivial String Problem

cf2209 E

观察题面

首先仔细研究题面到底什么意思，要把字符串拼接起来，而且每一段字符串都是这整个字符串的前缀，然后要计算一下对于每个前缀考虑这个过程的答案，字符串的题还涉及到前缀应该去考虑一下kmp，考虑一下复杂度，kmp取一遍next数组是线性的，这题q不大，nq可以接受所以看起来很能做，然后考虑一下具体过程。

研究与next的关系

首先根据dp状态，到第$i$个字符的时候最多的段数，然后要往后转移的话需要后面的那一串是这个字符串的前缀，然后考虑一下每个点从前面转移过来的过程，考虑从第$i$个点往前跳，那么跳的这一整段会是最短的一段与前缀相同的那一段后缀（因为要段数最多所以跳的更短一点好）。
证明一下为什么跳的更短比较好，假设此时$i$点前面有2段后缀与前缀相同，可以先跳到比较近的那里去，然后可以发现在长的那一段那里还能接着跳，因为也和前缀相同，所以肯定是跳最近的。
此时就有状态我们需要点$i$这个位置往前最短的与前缀相同的后缀，而kmp计算的是最长的，但是在刚才的证明里会给我们一点启发，有2段的这种情况其实我们后面转移过来的时候肯定会先走到后面那里，分类讨论一下。
对于点$i$这个位置的next数组
1.$next[i] = 0$ 那这个点没得跳的直接+1就行
2.$next[next[i]] = 0$ 那这个点的最短的与前缀相同的后缀就是next[i]。
3.以上都不是的时候说明前面至少有2段，可以利用一下之前得到的答案，就是$p[next[i]]$，找最短的过程就是找到不存在更短的后缀的那一个后缀，有一个传递性。$p[next[i]]$的答案如果前面还有更多的段也会是从前面那一段传递过来的。
最好画一下图方便理解。
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while (q--) {
    int l, r;
    int ans = 0;
    cin >> l >> r;
    string ns = s.substr(l, r - l + 1);
    vi nx = getNext(ns);
    vi p(r - l + 1);
    for (int i = 1; i < r - l + 1; i++) {
        if (nx[i] == 0) {
            p[i] = 0;
            //这里-1是因为存的是长度，但是具体下标要-1
        } else if (nx[nx[i] - 1] == 0) {
            p[i] = nx[i];
        } else p[i] = p[nx[i] - 1];
    }
    vi dp(r - l + 1);
    dp[0] = 1;
    for (int i = 1; i < r - l + 1; i++) {
        dp[i] = dp[i - p[i]] + 1;
        ans += dp[i];
    }
    cout << ans + 1 << endl;
}