SP21360 题解

RainyRadio · 2023-10-02 14:34:32 · 题解

In Luogu

一道很好的字符串题。通过此题可以更深刻理解 KMP。

Solution

这道题与 P2375 动物园 很接近。

题目要求有多少个真后缀也是前缀，那熟悉 KMP 的同学就会很容易想到：这不就是 Border 嘛！问题就转化为求一个字符串中所有的 Border。

可以发现一个性质：先选择一个最长的 Border，然后在这个最长的 Border 里继续找次长的 Border，以此类推，最后我们便遍历了整个字符串所有的 Border。这个性质可以自行画图理解。

那么就很容易做了。先求一遍 next 数组，然后从 next_n 开始，不断往下走，最后遍历完所有的 Border，答案即为往下走了几次。

Code

void PRE()
{
    //get next
    nx[1] = 0;
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && s[j + 1] != s[i]) j = nx[j];
        if (s[j + 1] == s[i]) ++ j;
        nx[i] = j;
    }
}

void GetNUM()
{
    //不断往下走
    int j = nx[n];
    while (j) ++ ans, j = nx[j];
    cout << ans << '\n';
}

void solve()
{
    ans = 0;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    PRE(), GetNUM();
}