Hdu 1711 Number Sequence(KMP模板题)

缺乏、安全感 2022-05-19 06:56 179阅读 0赞

[传送门][Link 1]

题意：给你一个长度为N的文本串（1 <= N <= 1000000），和一个长度为M的模式串（1 <= M <= 10000），如果文本串中不存在模式串就输出 -1，否则输出该模式串在文本串里第一次出现的位置，**注意：这题输出的下标是从1开始的，所以数组下标要+1**。

分析：很明显这题我们不能用常规的暴力匹配，那样的话，复杂度是O(M\*N)，很明会超时，其实这题就是kmp裸题（模板题），如果不懂KMP是什么的，可以[参考这里][Link 2]，我们先预处理模式串的Next数组，复杂度是O(M)，然后根据这个Next数组让模式串和文本串匹配一遍，扫一遍的复杂度是O(N)，所以总的复杂度为O(M+N)。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6+5;
    int t[maxn],p[maxn];
    int Next[maxn];
    int lent,lenp;
     
    /**预处理模式串的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;
        while(i<lent)
        {
            if(j==-1||t[i]==p[j])
            {
                i++;
                j++;
            }
            else j= Next[j];
            if(j==lenp)    /**如果长度等于模式串的长度,则说明匹配成功*/
            {
                return i-j+1; /**这里注意下标要再加上1*/
            }
        }
        return -1;
    }
     
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&lent,&lenp);
            for(int i=0;i<lent;i++) scanf("%d",&t[i]);
            for(int i=0;i<lenp;i++) scanf("%d",&p[i]);
            getNext();
            printf("%d\n",kmp());
        }
        return 0;
    }

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