题解：P6080 [USACO05DEC] Cow Patterns G

· · 题解

P6080 [USACO05DEC] Cow Patterns G

做法：树状数组+kmp

前言

最近在学习 kmp，这题看了很久都没有弄明白，弄懂之后且当作记录一下思路吧（也是本蒟蒻第一篇题解）。

题意

对于两个数串 A 和 B，在 A 中找出所有长度等于 B 的子串，使这个子串与 B 中每个位置对应数在各自串中的相对排名都对应相等。

思路

tip1：排名

首先要考虑如何维护排名，我最先想到的就是离散化，但是这个题目需要动态维护子串排名，感觉不太可行。

因此可以利用树状数组或者线段树，查询对应下标的前缀和，就可以查出小于等于自己的有几个数，而且可以动态维护，易于删点增点。

树状数组比较简单好搓，那么我们用树状数组，简单写一个单点修改，前缀查询，就可以达到我们的目的。

tip2：kmp

剩下的就是爆改 kmp 了，我们考虑求 Next 数组的部分。

需要看对于前后两个子串，对于后子串中末尾（即为 i 指针）的地位，与前子串中末尾 j 指针的地位是否相同，这便是我们判断是否匹配的条件。

需要注意的是，由于会出现重复的数字，所以我们需要维护每个数以及每个数前面的一个数的排名，这样就相当于变相的记录了与自己相同的数的个数了（后减去前）。

由于前子串是顺着来的，所以我们可以提前预处理出来每个子串的排名，用两个 Rank 数组标记即可。

另一部分同理，记得及时删点。

代码

class Solution_Case //我的小习惯
{
    /*
    1.统计排名可以利用树状数组或者线段树，不用非要离散化（无法动态维护）
    查询对应下标的前缀和，就可以查出前面有几个数字，而且可以动态维护
    2.动态维护后子串的排名，需要删除前面的数，即add-1
    */
};

#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define N 500005
using namespace std;

int n, m, s, cnt;
int A[N], B[N];
int Rank1[N], Rank2[N];
int Next[N], ans[N];

class BIT //树状数组，单点修改，前缀查询
{
  public:
    int bitSum[N];
    void Add(int x, int val)
    {
        for (; x <= s; x += lowbit(x)) bitSum[x] += val;
    }
    int Query(int x, int ans = 0)
    {
        for (; x; x -= lowbit(x)) ans += bitSum[x];
        return ans;
    }
    bool Check(int x, int y)
    {
        //这里是为了应对重复的值，查询前一位，确保地位完全相同
        //变相的相当于记录了与自己相同的有多少个（Rank1-Rank2）
        return (Query(y) == Rank1[x]) && (Query(y - 1) == Rank2[x]);
    }
} Bit;

void Make_Next()    //处理出next数组
{
    memset(Bit.bitSum, 0, sizeof(Bit.bitSum));
    for (int i = 2, j = 0; i <= m; ++i)
    {
        //printf("j=%d i=%d\n", j, i);
        Bit.Add(B[i], 1);
        while (j && !Bit.Check(j + 1, B[i])) //失配
        {
            //删掉前面的点，因为要维护后子串的排名
            //printf("k=%d~%d add-1\n", i - j, i - Next[j]);
            for (int k = i - j; k < i - Next[j]; ++k)  Bit.Add(B[k], -1);
            j = Next[j];
        }
        if (Bit.Check(j + 1, B[i]))  ++j;
        Next[i] = j;
    }
}

void Cul_Ans()  //计算答案
{
    memset(Bit.bitSum, 0, sizeof(Bit.bitSum));
    for (int i = 1, j = 0; i <= n; ++i)
    {
        Bit.Add(A[i], 1);
        while (j && !Bit.Check(j + 1, A[i])) //失配
        {
            for (int k = i - j; k < i - Next[j]; ++k)  Bit.Add(A[k], -1);   //删点
            j = Next[j];
        }
        if (Bit.Check(j + 1, A[i]))  ++j;

        if (j == m) //整个串匹配完毕
        {
            ans[++cnt] = i - m + 1;

            //匹配上了以后要向前跳继续匹配，所以仍要删点
            //printf("k=%d~%d add-1\n", i - j, i - Next[j]);
            for (int k = i - j + 1; k <= i - Next[j]; ++k)  Bit.Add(A[k], -1);
            j = Next[j];
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; ++i)  scanf("%d", &A[i]);

    //维护出B的每个前缀中末尾的排名，在kmp时候要用
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &B[i]), Bit.Add(B[i], 1);
        Rank1[i] = Bit.Query(B[i]), Rank2[i] = Bit.Query(B[i] - 1);
    }

    Make_Next();
    Cul_Ans();
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i)  printf("%d\n", ans[i]);
    return 0;
}

小结

在我个人看来 kmp 这一算法很难理解，建议各位像我一样的初学者们多在纸上模拟模拟过程，千万不要不求甚解，争取弄明白（毕竟对着枯燥的课件确实难看懂）。

感谢各位耐心看完！