美妙的字符串之KMP算法

Cytheria ·

更新时间:2024-09-21

· 824 次阅读

概述

讲解非常非常详细的KMP算法
在S串中查找P串的位置所在

暴力算法：S:i， P:j
若s[i] == p[j],i++,j++;
若s[i]!=p[j], i = i-（j-1）+1, j = 0;
之前的已匹配段回溯肯定导致失配，因为p[0]!=p[last（当前不匹配的j位置）-1];

KMP算法：i不回退，只需要移动j。
1. 对模式串进行处理：next[j]是不匹配时的j下一步回溯位置，取决于当前字符的字符串中有最大长度的相同前缀后缀。
2. 对模式串P的处理：i从0-plen-1，遍历得到next[], 当某个字符失配时，该字符对应的next值会告诉你下一步匹配中，模式串应该跳到那个位置，如果next[j] = 0或者-1，则跳到模式串的开头字符，若next[j] = k 且k>0，代表下次匹配跳到j之前的某个字符，而不是跳到开头，且具体调过来k个字符。

 	  int next[1000000+100];
 	  void kmp_pre(char x[], int n){
 		int i, j;
 		i= 0；
 		j = next[0] = -1;
 		while(i < n){
 			while(j!=-1 && x[i]!=x[j]) j = next[j];
 			next[++i] = ++j;				
 		}
 	  }

int KmpSearch(char *s, char *p){
	int i =0;
	int j = 0;
	int slen = strlen(s);
	int plen = strlen(p);
	while(i < slen && j < plen){
		if(j == -1 || s[i] == p[j]){  i++; j++;}
		else {j = next[j];}
	}
}
if(j == plen) return i-j+1;
else return -1;

My 模板


#include
#include
#include
#include
#define MAXN 1000005
#define MAXNP 10005
using namespace std;
int s[MAXN], p[MAXNP];
int slen, plen;
void getnext(int next[]){
    int i = 0; int j;
    j = next[0] = -1;
    while(i < plen){
        while(j!=-1 && p[i]!=p[j]) j = next[j];//若不匹配，跳回直到前面匹配
        next[++i] = ++j;//回溯到下一个字符开始匹配，所以++j；
                        //i表示以i为最后一个字符为字符串的前缀匹配，++i的next值为找到的回溯
    }
}
int KMPsearch(int next[]){
    int i = 0; int j = 0;
    while(i < slen && j < plen){
        if(j == -1 || s[i] == p[j]){
            i++; j++;
        }
        else j = next[j];
    }
    if(j == plen){return i-j+1;}
    else return -1;
}
int main(){
    int next[10005];
    int t; scanf("%d", &t);
    while(t--)
    while(scanf("%d%d", &slen, &plen)==2){
        for(int i = 0; i < slen; i++) scanf("%d", &s[i]);
        for(int i = 0; i < plen; i++) scanf("%d", &p[i]);
        getnext(next);
        int ans = KMPsearch(next);
        printf("%d\n", ans);
    }
    return 0;
}

作者：be a ACMer

kmp算法 kmp 字符字符串

1024 个赞