主串S: [0...n-1]
模式串T: [0...m-1]
模式匹配：返回模式串在主串中的位置
蠻力法
int IndexMatch(char s[],char t[])
{
int n=strlen(s);
int m=strlen(t);
for(int i=0;i<=n-m;i++)
{
int j=0;
while(j<m && s[i+j]==t[j])
j++;
if(j==m) return i;
}
return -1;
}
簡單模式匹配算法的最壞時間復(fù)雜度為O(nm).
KMP算法
kmp算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的开财。每當一趟匹配過程中出現(xiàn)字符不相等時席舍，不需要回溯 i 指針惧互，而是通過修改 j 指針鸦概，將模式串向右盡可能遠的滑動一段距離梨撞，繼續(xù)進行比較何鸡。具體就是實現(xiàn)一個next()函數(shù)肆良，函數(shù)本身包含了模式串的局部匹配信息筛璧。
kmp算法通過一個O(m)的預(yù)處理，是匹配的時間復(fù)雜度降為O(n+m).
詳細推導(dǎo)過程可參考博客：https://www.cnblogs.com/yjiyjige/p/3263858.html
next[j]表示當S[i] != T[j] 時惹恃，模式串中需要重新和主串匹配的位置夭谤。
#include<iostream>
#include<cstring>
using namespace std;
const int N=100000;
int Next[N];
char s[N],t[N];
int slen,tlen;
//next[j]表示當s[i]!=t[j]時,模式串t中需要重新和主串匹配的位置
void makeNext()
{
int j,k;
j=0, k=-1;
Next[0]=-1;
while(j<tlen)
{
if(k==-1 || t[j]==t[k]) //當k為-1時,需要移動j,同時k要置0
{
Next[++j]=++k;
}else k=Next[k];
}
}
//返回模式串t在主串s中首次出現(xiàn)的下標
int kmpIdx()
{
int i=0,j=0;
while(i<slen && j<tlen)
{
if(j==-1 || s[i]==t[j]) //當j為-1時,要移動的是i,當然j也應(yīng)置0
{
i++; j++;
}else j=Next[j]; //i不需要回溯,j回溯到指定位置
}
if(j==tlen)
return i-tlen;
else return -1;
}
//返回模式串t在主串s中出現(xiàn)的次數(shù)
int kmpCnt()
{
int ans=0;
int i,j;
if(slen==1 && tlen==1)
{
if(s[0]==t[0]) return 1;
else return 0;
}
j=0;
for(i=0;i<slen;i++)
{
while(j>0 && s[i]!=t[j])
{
j=Next[j];
}
if(s[i]==t[j])
j++;
if(j==tlen)
{
ans++;
j=Next[j];
}
}
return ans;
}
int main()
{
cin>>s>>t;
slen=strlen(s);
tlen=strlen(t);
makeNext();
cout<<"模式串在主串中首次出現(xiàn)的位置:"<<kmpIdx()<<endl;
cout<<"模式串在主串中出現(xiàn)的次數(shù):"<<kmpCnt()<<endl;
return 0;
}
