hdu 1711 KMP模版题

冷不防 2022-07-26 05:23 111阅读 0赞

[点击打开链接][Link 1]

题意: 找模式串在文本串中首次出现的位置;

分析:, 数据量比较大, 因此要用KMP来解决,套上KMP模版就行了;

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=1000110;
    
    int Next[10010];
    int a[N],b[N/10];
    int main()
    {
        int T=in();
        while(T--)
        {
            int n=in(),m=in();
            for(int i=0;i<n;i++) scanf("%d",a+i);
            for(int i=0;i<m;i++) scanf("%d",b+i);
            int k=-1,j=0;
            Next[0]=-1;
            while(j<m)
            {
                if(k==-1 || b[k]==b[j]) Next[++j]=++k;
                else k=Next[k];
            }
            int i=0;
            j=0;
            while(i<n && j<m)
            {
                if(j==-1 || a[i]==b[j]) i++,j++;
                else j=Next[j];
            }
            if(j==m) printf("%d\n",i-j+1);
            else puts("-1");
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1711

发表评论取消回复

表情：

评论列表（有 0 条评论，111人围观）

还没有评论，来说两句吧...

相关阅读

相关 [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher A - Number Sequence HDU - 1711 (kmp)

\[kuangbin带你飞\]专题十六 KMP & 扩展KMP & Manacher A - Number Sequence HDU - 1711 题目链接

小鱼儿/ 2023年08月17日 15:41/ 0 赞/ 80 阅读

相关 HDU 1711 Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768

淩亂°似流年/ 2022年09月29日 15:53/ 0 赞/ 113 阅读

相关 HDU 1711 Number Sequence //简单kmp

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (

忘是亡心i/ 2022年08月23日 11:54/ 0 赞/ 127 阅读

相关 hdu 1711 KMP模版题

[点击打开链接][Link 1] 题意: 找模式串在文本串中首次出现的位置; 分析:, 数据量比较大, 因此要用KMP来解决,套上KMP模版就行了;

冷不防/ 2022年07月26日 05:23/ 0 赞/ 112 阅读

相关 hdu1711 Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (

亦凉/ 2022年05月30日 06:25/ 0 赞/ 141 阅读

相关 HDU - 1711 Number Sequence （KMP）

Number Sequence Problem Description Given two se

ゞ浴缸里的玫瑰/ 2022年05月19日 07:50/ 0 赞/ 179 阅读

相关 Hdu 1711 Number Sequence(KMP模板题)

[传送门][Link 1] 题意：给你一个长度为N的文本串（1 <= N <= 1000000），和一个长度为M的模式串（1 <= M <= 10000），如果文本串中不存在

缺乏、安全感/ 2022年05月19日 06:56/ 0 赞/ 169 阅读

相关 HDU 1711 Number Sequence——————KMP 模板题

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (

素颜马尾好姑娘i/ 2022年05月16日 08:54/ 0 赞/ 139 阅读

相关 kmp1-HDU1711 HDU1686 HDU2087 HDU3746

HDU 1711 kmp模板题 [http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_sh

叁歲伎倆/ 2022年05月14日 11:24/ 0 赞/ 132 阅读

相关 hdu1711(kmp纯模板)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] void get\_next() \{ int

Dear 丶/ 2021年12月22日 09:55/ 0 赞/ 157 阅读