一：BF算法
如果讓你寫字符串的模式匹配，你可能會(huì)很快的寫出樸素的bf算法，至少問題是解決了，我想大家很清楚的知道它的時(shí)間復(fù)雜度為O（MN），原因很簡單，主串和模式串失配的時(shí)候，我們總是將模式串的第一位與主串的下一個(gè)字符進(jìn)行比較，所以復(fù)雜度高在主串每次失配的時(shí)候都要回溯，圖我就省略了。
二：KMP算法
剛才我們也說了，主串每次都要回溯，從而提高了時(shí)間復(fù)雜度，那么能不能在“主串”和“模式串”失配的情況下，主串不回溯呢？而是讓”模式串“向右滑動(dòng)一定的距離，對(duì)上號(hào)后繼續(xù)進(jìn)行下一輪的匹配，從而做到時(shí)間復(fù)雜度為O（M+N）呢？所以kmp算法就是用來處理這件事情的。
代碼：
#pragma once
#include <iostream>
// --- 樸素匹配算法 ---
int NaiveMatch(const char * txt, const char * pat)
{
int nTxtLength = strlen(txt);
int nPatLength = strlen(pat);
int nTxt = 0;
int nPat = 0;
int nCount = 0; // 計(jì)數(shù)
while (nTxt <= nTxtLength - nPatLength && nPat < nPatLength)
{
++nCount;
if (pat[nPat] == txt[nTxt+nPat])
{
++nPat;
}
else
{
++nTxt;
nPat = 0;
}
}
std::cout << "NaiveMatch, compare counts: " << nCount << std::endl;
return (nPat == nPatLength ? nTxt : -1);
}
// --- KMP 匹配算法 ---
void GetNext(const char* pattern, int next[])
{
next[0] = 0;
int j = 0;
for (int i = 1; i < strlen(pattern); i++)
{
while( j > 0 && pattern[j] != pattern[i] )
{
j = next[j-1];
}
if (pattern[j] == pattern[i])
j++;
next[i] = j;
}
}
int KMPMatch(const char* src, const char* pattern, int next[])
{
int nSrc = 0;
int nPattern = 0;
int nCount = 0; // 計(jì)數(shù)
while(nSrc < strlen(src) && nPattern < strlen(pattern))
{
++nCount;
if (0 == nPattern || src[nSrc] == pattern[nPattern])
{
++nPattern;
++nSrc;
}
else
{
nPattern = next[nPattern];
}
}
std::cout << "KMP, compare counts: " << nCount << std::endl;
return (nPattern == strlen(pattern) ? nSrc - nPattern : -1);
}
#define PRINT_RESLUT(v) { if(-1 == (v)) std::cout << "No Find!"; else std::cout << "Position = " << (v); std::cout << std::endl << std::endl; }
int main()
{
const char* Src = "abc1aabc1aabc1aaababc1aababc1aabc1aaabc1aabc1aababc1aaabaabcbc1aa";
const char* Pattern = "abaabc";
int nPos = -1; // 保存匹配到的位置
/// 樸素匹配算法
nPos = NaiveMatch(Src, Pattern);
PRINT_RESLUT(nPos);
/// KMP匹配算法
int next[6] = {0};
GetNext(Pattern, next);
nPos = KMPMatch(Src, Pattern, next);
PRINT_RESLUT(nPos);
system("pause");
return 0;
}
運(yùn)行結(jié)果：
果.jpg)
疑惑：為什么KMP的效率會(huì)更低？
