kmp.txt

实现KMP算法。 经典的模式搜索算法。

#include <iostream>
#define MAXSIZE 15
using namespace std;

char P[MAXSIZE] = {0};
char T[MAXSIZE] = {0};
int next[MAXSIZE] = {0};
void MyNext(char P[], int next[], int length);

int main()
{
    int i = 1;
    int lengthP = 0;
	int lengthT = 0;

	cout << "Input the long string:" <<endl;
	P[i] = getchar();
    while (P[i] != '\n')
	{
		i++;
		P[i] = getchar();
		lengthP++;
	}
	cout << "The next() is:" << endl; 
    MyNext(P, next, lengthP);
    for (i=1; i<=lengthP; i++)
        cout << next[i];
	cout << endl;

	cout << "Input the shot string:" <<endl;
    T[i] = getchar();
    while (T[i] != '\n')
	{
		i++;
		T[i] = getchar();
		lengthT++;
	}

	return 0;
}

void MyNext(char P[], int next[], int length)
{
    int m = length;
    int k  = 0;
	
	next[1] = 0;
    for (int q=2; q<=m; q++)
    {
        while (k>0 && (P[k+1] != P[q]))
            k = next[k];

		if (P[k+1]==P[q])
			k++;
		
        next[q] = k;
    }
}

int MyKMP(char P[], char T[], int next[], int lengthP, int lengthT)
{
	int n = lengthP;
	int m = lengthT;
	int q = 0;
	
	for (int i=1; i<=n; i++)
	{
		while (q>0 && P[q+1] != T[i])
			q = next[q];

		if (P[q+1] == T[i])
			q++;

		if (q == m)
			cout << "Pattern occurs with shift" << i << endl;

		q = next[q];
	}
}