[笔记] KMP算法

  • A+
所属分类:C++学习

算是一个比较简单的算法吧,主要思想就是空间换时间。挺早之前在知乎上看到一篇文章写的不错,看懂了个大概,但是还没写过。于是趁有时间(偷懒)写了个简单的例子,备忘。

https://www.zhihu.com/question/21923021/answer/1032665486

算法图示

[笔记] KMP算法
预处理模式串,计算失配后的会退位置

code

#include<cstdio>
#include<cstring>
#include<iostream>

#define MANLEN 1024

char txt[MANLEN];
char pat[MANLEN];
int next[MANLEN];

void Getnext(const char *raw){
    int len = strlen(raw);
    int x = 1; //遍历pattern串与now作比较
    int now = 0; //永远指向当前最长前缀的下一位
    next[0] = 0; 
    while(x<len){
        if( raw[x] == raw[now]){
            now++;
            next[x++]=now;
        }
        else
            if(now)
                now=next[now-1];
            else{
                next[x]=0;
                x++;
            }
    }
    puts("next: ");
    for(int i=0;i<len;i++)
        printf("%d ",next[i]);
    puts("\n-----------");
}

void KMP(const char *txt,const char *pat){
    int N=strlen(txt);
    int M=strlen(pat);
    printf("txt_len:%d  pat_len:%d\n",N,M);
    for(int i=0,j=0;i<N;i++){ //在这个算法中,一定不会出现重复比较
        if(txt[i]==pat[j]){
            j++;
            if(j==M){ //发现完配串,输出位置(主串绝对位置-模式串偏移)
                printf("index: %d\n",i+1-j);
                j=0;
            }
        }
        else
            j=next[j]; //失配时把j移到最长重复前缀的下一位
    }
}

int main(int argc,char *argv[]){
    puts("txt:");
    scanf("%s",txt);
    puts("pat:");
    scanf("%s",pat);
    Getnext(pat);
    KMP(txt,pat);
    return 0;
}

如果有漏洞或者什么值得优化的地方欢迎指正!

eqqie

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:1   其中:访客  1   博主  0

    • xtsrxpbjfw xtsrxpbjfw 0

      [笔记] KMP算法 | 赤道企鹅的博客
      xtsrxpbjfw http://www.g9p33q9f1x1c7gy66us1q3yo448uqm88s.org/
      [url=http://www.g9p33q9f1x1c7gy66us1q3yo448uqm88s.org/]uxtsrxpbjfw[/url]
      axtsrxpbjfw