KMP演算法總結（南昌理工ACM集訓）
（這幾天想題目想的腦殼疼）
-
什么是KMP演算法
（我準備參考別人的話，講滴非常好）
Knuth-Morris-Pratt字串查找演算法（簡稱為KMP演算法，0.0）可在一個主文本字串S內查找一個詞W的出現位置，
此演算法通過運用對這個詞在不匹配時本身就包含足夠的資訊來確定下一個匹配將在哪里開始的發現，從而避免重新檢查先前匹配的字符，
-
為什么我們要用KMP演算法呢
我們先介紹一下普通匹配字串的演算法
題目
給定一個模式串S，以及一個模板串P，所有字串中只包含大小寫英文字母以及阿拉伯數字，
模板串P在模式串S中多次作為子串出現，
求出模板串P在模式串S中所有出現的位置的起始下標，
- 樸素演算法（暴力）
（借一下y總的模板題來用一下，哈哈）
#include<iostream>
using namespace std;
int main(){
string a,b;
cin>>a>>b;
for(int i=0;i<a.size()-b.size()+1;i++){
string c=a.substr(i,b.size());
if(c==b) cout<<i<<" ";
}
}
但是當字母長度很大時，就會超時，
于是KMP演算法就誕生了（哈哈，問題造就演算法）
- -KMP演算法解決
等等等一下，我先介紹怎么用KMP演算法
- 原理
母串 abcdabc
字串 abc
我們如果用樸素演算法的話，就是一個一個從母串中找，
但是我們讓一個字串匹配了很多次，很浪費效率，大大提高了時間，
比如
母串 abcdabc
字串 abc
母串 abcdabc
字串 *abc
母串 abcdabc
字串 **abc
母串 abcdabc
字串 ***abc
母串 abcdabc
字串 ****abc
這樣匹配很重復，字符需要匹配多次 （難過呀）
-
kmp演算法實作
kmp演算法由兩個東西組成 next陣列和 kmp匹配， -
next陣列是什么呢
next陣列主要儲存的是子串的前后綴的位置
在p字串中
p [1- j ] = p [ i - j + 1 , i]; -
kmp匹配
這是子串和母串進行匹配，通過next陣列避免一個字符多次重復的匹配 -
模板
//next陣列
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}
// kmp匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
// 匹配成功后的邏輯
j = ne[j];
}
}
大家是不是覺得很簡單，如果明白可以做一下這道題
【模板】KMP字串匹配
這樣你已經有了一點入門的知識了~~（因為KMP演算法遠沒有這么簡單，哈哈）~~
現在我們必須加大難度對于你們對KMP演算法的了解了
熟練掌握next陣列，這道題了解一下
做完了，看來你現在已經有一定的框架了
來一道CF的KMP試試吧
這道題比較全面的展現了kmp的強大
這個題比較具體的闡述了next陣列和kmp匹配
看看我的AC代碼 （AC時的喜悅，哈哈）
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int q[]={1,2,3};
char p[4][N];
int ne[4][N];
int k[4][4];
int len[4];
int ans=0x7fffffff;
void getnext(int m,char p[],int k){
for(int i=2,j=0;i<=m;i++){
while(j&&p[i]!=p[j+1]) j=ne[k][j];
if(p[i]==p[j+1]) j++;
ne[k][i]=j;
}
}
int kmp(int n,int m,char s[],char p[],int k){
int j=0;
for(int i=1;i<=n;i++){
while(j&&s[i]!=p[j+1]) j=ne[k][j];
if(s[i]==p[j+1]) j++;
if(j==m) return -1;
}
return j;
}
void solve(int i,int j,int l){
if(k[i][j]>=0&&k[j][l]>=0) ans=min(ans,len[i]+len[j]+len[l]-k[i][j]-k[j][l]);
else{
if(k[i][j]<0&&k[j][l]<0) ans=min(ans,len[l]);
else if(k[i][j]<0) ans=min(ans,len[j]+len[l]-k[j][l]);
else if(k[j][l]<0) ans=min(ans,len[i]+len[l]-k[i][l]);
}
}
int main(){
scanf("%s%s%s",p[1]+1,p[2]+1,p[3]+1);
for(int i=1;i<=3;i++) len[i]=strlen(p[i]+1);
for(int i=1;i<=3;i++){
getnext(len[i],p[i],i);
for(int j=1;j<=3;j++){
if(i==j) continue;
k[i][j]=kmp(len[j],len[i],p[j],p[i],i);
}
}
do{
solve(q[0],q[1],q[2]);
}while(next_permutation(q,q+3));
cout<<ans;
return 0;
}
學習快樂，演算法漫漫路，我很開心~~（Orz，來救救我）~~
萌新的一點點總結，歡迎大佬來指點0.0
點個贊吧，我打的很辛苦滴 看看孩子吧/(ㄒoㄒ)/~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249437.html
標籤：其他
上一篇：關于經濟學家的笑話
下一篇：Api介面-笑話段子短視頻精選集