KMP演算法
- 用于改進字串匹配演算法
字串匹配
- 主串中是否存在模式串
模式匹配
- 基本思想
- 從模式串的第一個字符和主串的第一個字符比較
- 不同時又從模式串的第一個字符和主串的第二個字符比較
- 直到匹配成功或匹配不成功
- 總結:太慢
KMP
- 基本思想
- 在模式匹配中若\(S[i]==P[j]\)
- 匹配\(S[i+1],P[j+1]\)
- 若\(S[i]!=P[j]\)
- 將模式串右移至\(nx[j]\)
- 即比較\(S[i],P[nx[j]]\)
- 重復上述程序至\(j==m,i==n\)結束
- 在模式匹配中若\(S[i]==P[j]\)
- \(nx[]\)陣串列示在一次匹配不成功的情況最多可在模式串中向前跳幾個字符
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int Max=100010;
int nx[Max];
//前綴陣列(或next[]),
//表示在這一次匹配不成功的情況最多可在模式串中向前跳幾個字符
//也描述了模式串的對稱程度
string S;//主串
string P;//模式串
int T,N,M,ans;
void makenx(int M)//模式串
{//計算前綴陣列
int i=0,j=-1;
//i表示當前計算的是第幾個(即前綴陣列的下標)
//j表示能跳到第幾個(即前綴陣列的值)
nx[i]=j;
//在第0個字符就匹配不成功,nx[0]=-1,
//也就是說在第0個字符就匹配不成功時,匹配主串的下一個字符
while(i<M)//計算完時跳出回圈
if(j==-1||P[i]==P[j])
//j==-1時,表示沒有字符和第i個字符相同
//p[i]==p[j]表示當前字符(i)和字符(j)匹配
i++,j++,nx[i]=j;
//以上兩種情況都要記錄nx[]值即nx[i]=j
//注意這里是先加后記錄,
//如果s[]!=p[i+1],因為P[i]==P[j],可以比較S[]與P[j+1],即nx[i+1]=j+1;
//j==-1時,此時如果S[]!=P[i+1]時,因nx[i+1]=j+1=0,即重新匹配S[0]
else
j=nx[j];
//當不滿足以上兩種情況時,即j!=-1,且P[i]!=P[j]
//應該向前找是否相同
}
int Kmp(int N,int M)//KMP匹配演算法
{
int i=0,j=0,ans=0;
//i表示主串下標
//j表示當前匹配到模式串的哪一位
//ans表示有幾個重復子串
while((i<N)&&(j<M))
//比較完時跳出回圈
//i跳出回圈表示主串回圈完
//j跳出回圈表示模式串匹配完
{
if(j==-1||S[i]==P[j]) i++,j++;
//重新匹配或匹配成功時i++,j++
else j=nx[j];//不成功時向前跳進行重新匹配
// if(j==M) ans++,j=nx[M-1],i--;用于計算幾個重復子串(模式串)
}//
if(i>=M) return i-M;//下標運算
else return -1;//匹配失敗
// return ans;
}
int main()
{
scanf("%d",&T);//次數
while(T--)
{
cin>>S>>P;//輸入
N=S.size();M=P.size();
makenx(M);ans=Kmp(N,M);
cout<<ans<<endl;//輸出
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71513.html
標籤：C++