CF432D Prefixes and Suffixes

传送门

Solution

使用扩展 KMP 求出 $z_i$。设字符串 $S$ 长度为 $n$，下标从 $0$ 开始。某前缀同时也是后缀，当且仅当 $i+z_i=n$。 符合要求的 $z_i$ 数量即为完美子串数量。$z_i$ 对应的完美字串在 $S$ 中的出现次数，等于满足 $j\neq i$ 且 $z_j\ge z_i$ 的 $j$ 数量。可用权值树状数组计算 $j$ 的数量。

时间复杂度 $O(n\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int z[N], l, r, ans[N], ans_cnt, tr[N], n, cntn;
string s;

int lowbit(int x) {return x & -x;}

void add(int x, int c)
{
    for (; x <= n; x += lowbit(x))
        tr[x] += c;
}

int query(int x)
{
    int res = 0;
    for (; x > 0; x -= lowbit(x))
        res += tr[x];
    return res;
}

int main()
{
    cin >> s; n = s.size();
    cntn = n - 1;
    for (int i = 1; i < n; i++) {
        if (i <= r && z[i - l] < r - i + 1)
            z[i] = z[i - l];
        else {
            z[i] = max(r - i + 1, 0);
            while (i + z[i] < n && s[i + z[i]] == s[z[i]])
                ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i; 
            r = i + z[i] - 1;
        }
        if (i + z[i] == n)
            ans[++ans_cnt] = z[i];
        if (z[i] > 0)
            add(z[i], 1);
        else 
            --cntn;
    }
    sort(ans + 1, ans + ans_cnt + 1);
    printf("%d\n", ans_cnt + 1);
    for (int i = 1; i <= ans_cnt; i++) {
        add(ans[i], -1);
        int cnt = cntn - 1 - query(ans[i] - 1);
        add(ans[i], 1);
        printf("%d %d\n", ans[i], cnt + 2);
    }
    printf("%d 1\n", n);
    return 0;
}