KMP模板

╰+攻爆jí腚メ 2021-12-20 23:57 201阅读 0赞

1 #include <iostream>
     2 #include <string>
     3 using namespace std;
     4 /* P 为模式串，下标从 0 开始 */
     5 void GetNext(string P,int next[]){
     6     int p_len=P.size();
     7     int i=0;   // P 的下标
     8     int j=-1;
     9     next[0]=-1;
    10 
    11     while(i<p_len-1){
    12         if (j == -1 || P[i] == P[j]){
    13             i++;
    14             j++;
    15             next[i]=j;
    16         }
    17         else
    18             j=next[j];
    19     }
    20 }
    21 
    22 /* 在 S 中找到 P 第一次出现的位置 */
    23 int KMP(string S,string P,int next[]){
    24     GetNext(P, next);
    25     int i=0;  // S 的下标
    26     int j=0;  // P 的下标
    27     int s_len=S.size();
    28     int p_len=P.size();
    29     while (i<s_len&&j<p_len){
    30         if (j==-1||S[i]==P[j]){  // P 的第一个字符不匹配或 S[i] == P[j]
    31             i++;
    32             j++;
    33         }
    34         else
    35             j=next[j];  // 当前字符匹配失败，进行跳转
    36     }
    37 
    38     if (j==p_len)  // 匹配成功
    39         return i-j;
    40 
    41     return -1;
    42 }
    43 
    44 int main(){
    45     int n;
    46     int next[10000]={
        0};
    47     char a[10000],b[10000];
    48     cin>>a;
    49     cin>>b;
    50     if(KMP(a,b,next)==0){
    51         cout<<"yes\n";
    52     }
    53     else cout<<"no\n";
    54     return 0;
    55 }

转载于:https://www.cnblogs.com/Never-Land/p/10821852.html

发表评论取消回复

表情：

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

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

相关阅读

相关二、数据结构7：KMP 模板题+算法模板（KMP字符串）

文章目录算法模板 KMP题目模板模板题 KMP字符串原题链接题目

「爱情、让人受尽委屈。」/ 2023年10月14日 11:13/ 0 赞/ 72 阅读

相关 [模板] KMP算法/Border

KMP 算法 KMP (Knuth-Morris-Pratt) 算法是一种在线性时间内匹配文本串和模式串的算法. 称字符串的 Border 集合为 \\\[ \\op

雨点打透心脏的1/2处/ 2023年08月17日 17:16/ 0 赞/ 99 阅读

相关 KMP模板

include <stdio.h> void getnext(char ch, int next[]); int kmp(char ch1,

末蓝、/ 2022年09月20日 15:13/ 0 赞/ 171 阅读

相关 KMP模板

KMP算法是快速字符串匹配算法，朴素的暴力算法的时间复杂度为O（n\m），而KMP通过对模式串进行相应的处理，能够达到O（m+n）的速度。我们知道在字符串匹配的时候最消耗时

我不是女神ヾ/ 2022年08月10日 16:34/ 0 赞/ 165 阅读

相关 Number Sequence（kmp模板）

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

Bertha 。/ 2022年08月02日 13:39/ 0 赞/ 153 阅读

相关数据结构—KMP模板

/ 编写一个程序，实现顺序串的各种模式匹配运算，并完成下面功能：（1）建立目标串s "abcabcdabcdeabcdefabcdefg"和模式串t

╰+攻爆jí腚メ/ 2022年07月30日 13:13/ 0 赞/ 152 阅读

相关 KMP算法的几种模板

一、寻找子串首次出现的位置代码： C++ Code <table style="width:100%; font-family:'Consolas','Courie

快来打我*/ 2022年06月09日 01:09/ 0 赞/ 156 阅读

相关 KMP模板

/ pku3461(Oulipo), hdu1711(Number Sequence) 这个模板字符串是从0开始的 Next数组是从1开始的

╰+哭是因爲堅強的太久メ/ 2022年05月30日 06:24/ 0 赞/ 147 阅读

相关 hdu1711(kmp纯模板)

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

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

相关 KMP模板

1 include <iostream> 2 include <string> 3 using namespace std; 4 / P

╰+攻爆jí腚メ/ 2021年12月20日 23:57/ 0 赞/ 202 阅读