今天做了一個簡單的字串比對程式，功能是實現從 A 字串中刪除包含 B 最多的字元，例如 A=“aaaaabbbbbbabababa” B=“aaccbaab”，應當刪除 “aab”，而不是 aa，相信知道搜尋引擎的朋友肯定是知道的吧，這種演算法主要用於去除頁面中無效的關鍵字，來減少收錄的計算消耗的一種方法，好了，具體演算法明天拿出來吧，不過今天要講的是兩種比較常用的字串匹配演算法，KMP 演算法，索引法
KMP 演算法是 Knuth, Morris, Pratt 三位前輩提出的字串快速匹配演算法，簡稱 KMP 演算法，典的演算法了，還有以後發展的 BM 和 AB-BM 演算法，別急啊，這個下次再講，最近是沒時間寫部落格了，原理很簡單，就是使用了額外的數值記錄索引匹配的次數，然後根據這個結果進行結果計算的方法，不知道？可以參閱
http://www.chinaitpower.com/A/2003-01-04/45995.html
索引法，就數最簡單的字串匹配演算法，原理就是，一個一個試，找到第一個以後，再看是否匹配第二個了，一直到字串末尾，很經典的演算法。
下面我們作個簡單對比，看程式碼：
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
/*getnext*/
void getNext(char p[],int next[]){
int i, j, slen;
slen = strlen(p);
i = 0;
j = -1;
next[0] = -1;
while(i < slen){
if((j == -1) || (p[i] == p[j])){
i++;
j++;
next[i] = j;
}/*if*/
else{
j = next[j];
}/*else*/
}/*while*/
}/*get_next*/
int kmp(char s[], char p[], int pos, int next[]) {
/*KMP 演算法 */
int i, j, slen, plen;
i = pos;
j = 0;
slen = strlen(s);
plen = strlen(p);
while((i < slen) && (j < plen)){
if((j == -1) || (s[i] == p[j])){
i++;
j++;
}
else
{
j = next[j];
}
}/*while*/
if(j >= plen) {
return (i-plen);
}/*if*/
else {
return -1;
}/*else*/
}/*kmp*/
int index(char s[], char p[], int pos){
/* 索引匹配法 */
int i, j, slen, plen;
i = pos;
j = 0;
slen = strlen(s);
plen = strlen(p);
while((i < slen) && (j < plen)){
if((s[i] == p[j])){
i++;
j++;
}/*if*/
else{
i = i-j+1;
j = 0;
}/*else*/
}/*while*/
if(j >= plen) {
return (i-plen);
}
else {
return -1;
}
}/*index*/
void main(){
char s [] = "acbaabcaacabaabaabcacaabc"; /* 測試字串 */
char p[] = "abaabca";
int next[50];
getNext(p, next);
printf("found index at %dn", kmp(s, p, 0, next));
printf("found index at %dn", index(s, p, 0));
}/*main*/
KMP 演算法是 kmp () 這個函數，INDEX 演算法是 index () 函數，相信諸位看出來了吧，KMP 要多一個計算陣列的，這也是精髓所在，也是效率所在，提高了一個數量級，諸位知道這樣提高效率的結果了吧，不過，最壞的情況可能要浪費 N 多的空間了，好了，演算法提供完，演算法部分大家要是不懂的話，可以直接留言，或者跟我聯繫
附：來自網路的 KMP 匹配演算法 C++ 實現演算法，源自http://www.chinaitpower.com/A/2003-01-04/45995.html，作者莫怪，借用一下給大家參考，個人比較喜歡純 C，C++ 最近不怎麼使用了
KMP 演算法查找字串 S 中含字串 P 的個數 count
#include #include #include using namespace std;
inline void NEXT(const string& T,vector& next)
{
// 按模式字串生成 vector,next (T.size ())
next[0]=-1;
for(int i=1;i=0 )
j=next [j] ; // 遞推計算
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
// 利用模式字串 T 的 next 函數求 T 在主字串 S 中的個數 count 的 KMP 演算法
// 其中 T 非空，
vector next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index
system("PAUSE");
return 0;
}