版本一
#include <iostream>
using namespace std;
int* buildNext(char* pattern)
{
size_t m = strlen(pattern), j = 0;// "主"串指针
int* nTable = new int[m]; // next table
int t = nTable[0] = -1;
while(j < m-1)// 0 ~ m-1 arrary
{
if (0 > t || pattern[j] == pattern[t])
{
j++; t++;
nTable[j] = t;
}
else
t = nTable[t];
}
return nTable;
}
int match(char* pattern, char* t)
{
int* next = buildNext(pattern);// 构造next表
int n = strlen(t), i = 0;
int m = strlen(pattern), j = 0;
while(j < m && i < n)
{
if (0 > j || t[i] == pattern[j])// 匹配
{
i++; j++;// 转到下一对字符
}
else
{
j = next[j];// 模式串右移(主串不回退)
}
}
delete [] next;
return i - j;
}
int main()
{
char* t = "abcdefghijklmnopqrstuvwxyz0123456789";
char* pattern = "123";
int index = match(pattern, t);
cout << index << endl;
return 0;
}