《数据结构和算法》——KMP算法实现
利用一个next数组存储匹配串每一个位置的回溯下标，当用匹配串与被匹配串进行逐个比较时，若出现匹配错误，可以利用next数组快速回溯。next数组：当前缀和后缀一致时，记录一次下标；若不一致，固定后缀，回溯前缀直至最开始的下标0，记录下标1，表示需要从头开始匹配。利用next数组我们可以快速地根据匹配串中重复的部分减少匹配次数。
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;
void GetNext(char T[], int next[])
{
int i=1, j=0;
next = 0;
while (i < T)
{
if (0 == j || T == T)
{
i++;
j++;
if (T == T)
{
next = next;
}
else
{
next = j;
}
}
else
{
j = next;
}
}
}
void GetString(char str[])
{
int i;
char temp;
scanf_s("%c", &temp);
for (i = 1; temp != ' '&&temp != '\n'; i++)
{
str = temp;
scanf_s("%c", &temp);
}
str = i - 1 ;
}
int KMP(char S[], char T[],int next[])
{
int i=1,j=1;
int flag = 0;
while (i <= S )
{
if (j==0||S == T)
{
i++;
j++;
}
else
{
j = next;
}
if (j > T )
{
flag = 1;
break;
}
}
if (flag)return i;
else return 0;
}
int main()
{
char S, T ;
int next;
cout << "输入主串:";
GetString(S);
cout << "输入子串:";
GetString(T);
GetNext(T, next);
int pos = KMP(S, T, next)-T;
if (pos)cout << "YES,in the no." << pos << endl;
else cout << "NO"<< endl;
system("PAUSE");
}
页:
[1]