KMP
\(KMP\) 演算法是一種改進的字串匹配演算法，由 \(D.E.Knuth\) ， \(J.H.Morris\) 和 \(V.R.Pratt\) 提出的，簡稱 \(KMP\) 演算法，常用來解決可重疊的字串匹配問題，
基本原理
\(KMP\) 演算法的核心是利用匹配失敗后的資訊，盡量減少模式串與主串的匹配次數以達到快速匹配的目的，具體實作就是通過一個next陣列實作，陣列本身包含了模式串的區域匹配資訊，
首先對模式串進行自身匹配，得到next陣列，next[i]為滿足s2[i-z,...,i-1]=s2[0,...,z-1] 的最大z值，即s2的子串s2[0,...,i]最長公共前后綴的長度，
這樣在進行模式串與文本串的匹配時（假設當前為文本串的s1[i]與模式串的s2[j]進行匹配），一旦發生失配情況，可以只移動模式串而不回溯指標，移動時，只需要將s2[0,...,j-1]前綴移動到后綴的位置，然后，從模式串子串s2[0,...,j-1]前綴的下一位即第next[j]位開始與文本串當前位第i位進行匹配，
效率分析
一般情況下， \(KMP\) 演算法的期望時間復雜度為 \(O(n＋m)\) ，其中 \(n,m\) 分別是文本串和模式串的長度，
核心代碼
ll len1,len2,next[maxn],pos[maxn],ans;
string s1,s2;
void pre()
{
len2=s2.length();
ll j=0;
next[0]=0; /*初始化*/
for(ll i=1;i<len2;i++)
{
while(j&&s2[i]!=s2[j])j=next[j]; /*如果失配，模式串指標移到s2[0,...,j]前綴后一位*/
if(s2[i]==s2[j])j++; /*如果相同，長度+1*/
next[i+1]=j;
}
}
void KMP()
{
len1=s1.length();
pre();
ll j=0;
for(ll i=0;i<len1;i++)
{
while(j&&s1[i]!=s2[j])j=next[j]; /*如果失配，模式串指標移到s2[0,...,j]前綴后一位*/
if(s1[i]==s2[j])j++; /*如果相同，長度+1*/
if(j==len2) /*如果匹配到末尾*/
{
pos[++ans]=i-j+2; /*記錄匹配起始位置*/
j=next[j]; /*模式串指標移到s2[0,...,j]前綴后一位*/
}
}
return;
}
例題決議
洛谷 P3375 【模板】KMP字串匹配
給出一個文本串 \(s_1\) 和一個模式串 \(s_2\) ，求 \(s_2\) 在 \(s_1\) 中出現的所有位置并輸出前綴陣列，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define maxm 200005
#define INF 1234567890
#define p 1000000007
template<class T>inline bool reads(T &x)
{
register char c=getchar();
while(c==' '||c=='\n'||c=='\r'||c=='\t')c=getchar();
if(c==EOF)return false;
while(c!=' '&&c!='\n'&&c!='\r'&&c!='\t')x+=c,c=getchar();
return true;
}
template<class T>inline void print(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
template<class T>inline void print(T x,char c){print(x),putchar(c);}
ll len1,len2,next[maxn],pos[maxn],ans;
string s1,s2;
void pre()
{
len2=s2.length();
ll j=0;
next[0]=0;
for(ll i=1;i<len2;i++)
{
while(j&&s2[i]!=s2[j])j=next[j];
if(s2[i]==s2[j])j++;
next[i+1]=j;
}
}
void KMP()
{
len1=s1.length();
pre();
ll j=0;
for(ll i=0;i<len1;i++)
{
while(j&&s1[i]!=s2[j])j=next[j];
if(s1[i]==s2[j])j++;
if(j==len2)
{
pos[++ans]=i-j+2;
j=next[j];
}
}
return;
}
int main()
{
reads(s1),reads(s2);
KMP();
for(ll i=1;i<=ans;i++)print(pos[i],'\n');
for(ll i=1;i<=len2;i++)print(next[i],' ');
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/98149.html
標籤：C++