Hdu 1686 Oulipo(KMP入门)

墨蓝 2022-05-19 06:56 245阅读 0赞

[传送门][Link 1]

题意：给你一个长度为W的模式串(1 ≤ |W| ≤ 10,000)和一个长度为T的文本串(|W| ≤ |T| ≤ 1,000,000)，问你这个模式串在文本串中出现了几次，**注意样例里面的这一组样例AZA AZAZAZA 输出的是3而不是2，重复的也算一次**。

分析：显然根据HDU一贯的作风(套路)，这题我们肯定不能用朴素的暴力匹配，那样的话，复杂度是O(M\*N)，肯定会超时，其实这题就是kmp裸题（模板题），如果不懂KMP是什么的，可以[参考这里][Link 2]，我们先预处理模式串的Next数组，复杂度是O(M)，然后根据这个Next数组让模式串和文本串匹配一遍，扫一遍的复杂度是O(N)，所以总的复杂度为O(M+N)。这里需要注意一点的是：**当每次j等于了模式串的长度的时候不是让j回溯到0**，因为题目允许带重复的匹配（相当于要根据Next数组看前面已匹配了的情况）而预处理的时候其实已经存下了模式串的前后缀匹配情况，所以应该让j回溯到Next\[j\]。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6+5;
    char p[maxn],t[maxn];
    int Next[maxn];
    int lenp,lent;
    
    /**预处理模式串的Next数组*/
    void getNext()
    {
        int j = -1,i = 0;
        Next[0]=-1;
        while(i<lenp)
        {
            if(j==-1||p[i]==p[j])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else j=Next[j];
        }
    }
    
    int kmp()
    {
        int i = 0,j = 0,sum = 0;
        while(i<lent)
        {
            if(j==-1||t[i]==p[j])
            {
                i++;
                j++;
            }
            else j=Next[j];
            if(j==lenp)
            {
                sum++;
                j=Next[j];/**注意j应该这样回溯*/
            }
        }
        return sum;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%s%s",p,t);
            lenp=strlen(p),lent=strlen(t);
            getNext();
            printf("%d\n",kmp());
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1686
[Link 2]: https://blog.csdn.net/qq_41311604/article/details/79691658