[笔记] KMP算法

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

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

算法图示

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;
}

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