【HDU 1711】Number Sequence（裸KMP算法）

今天药忘吃喽~ 2023-06-01 14:58 21阅读 0赞

### 题目链接 ###

[题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_showproblem.php_pid_1711]

### 题意 ###

裸KMP算法

### 时间复杂度 ###

O(m+n)

### 代码如下（G++） ###

#include <iostream>
    #include "string.h"
    using namespace std;
    
    int a[1000010];
    int b[10010];
    int next0[10010];
    
    int T,N,M;
    void get_next(){
        int i = 0;int j = -1;
        next0[0] = -1;
        while(i < M){
            if(j == -1||b[i] == b[j]){
                i++;j++; next0[i] = j;
            }else{
                j = next0[j];
            }
    //        cout << i << " " << j << endl;
        }
    }
    
    int KMP(){
        int i = 0;int j = 0;
        while(i < N && j < M){
            if(j == -1 or a[i] == b[j])
                ++i,++j;
            else
                j = next0[j];
        }
        if(M == j) return i-j;
        else return -2;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin >> T;
    
        while(T--){
            cin >> N >> M;
            for(int i = 0;i < N; ++i) cin >> a[i];
            for(int j = 0;j < M; ++j) cin >> b[j];
            get_next();
            cout << KMP()+1 << endl;
        }
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/zhangjiuding/p/11485826.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1711]: http://acm.hdu.edu.cn/showproblem.php?pid=1711

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1711 Number Sequence （KMP模板题）

Number Sequence Problem Description Given two sequences of numbers : a\[1\], a\

谁借莪１个温暖的怀抱￠/ 2024年02月17日 21:12/ 0 赞/ 67 阅读

相关 [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 赞/ 126 阅读

相关【HDU 1711】Number Sequence（裸KMP算法）

题目链接 [题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1711][http_acm.hdu.edu.cn_showpr

今天药忘吃喽~/ 2023年06月01日 14:58/ 0 赞/ 22 阅读

相关 HDU 1711 Number Sequence

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

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

相关 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 赞/ 176 阅读

相关 HDU1711-Number Sequence

Number Sequence Problem Description Given two sequences of numbers : a\[

系统管理员/ 2022年06月03日 04:40/ 0 赞/ 144 阅读

相关 hdu1711 Number Sequence

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

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

相关 HDU - 1711 Number Sequence （KMP）

Number Sequence Problem Description Given two se

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

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

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

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

相关 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 赞/ 189 阅读