【C語言】【數據結構】串的模式匹配演算法（計算next、KMP演算法）

1.錄入多個字串計算並驗證NEXT值，輸入0結束。
2.用KMP演算法對主串和模式串進行模式匹配。

#include <stdio.h>
#include <stdlib.h>
#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

void get_next(SString , int *);
int Index_KMP(SString , SString );

int main()
{
	SString T, S;
	char ch;
	int n, i, j;
	int pos;
	
	printf("請輸入需要匹配的字串對數: \n");
	scanf("%d", &n);
	ch = getchar();
	for(i=1; i<=n; i++)
	{
		ch = getchar();
		for(j=1; j<=MAXSTRLEN && ch!='\n'; j++)
		{
			S[j] = ch;
			ch = getchar();
		}
		S[0] = j-1;
		ch = getchar();
		for(j=1; j<=MAXSTRLEN && ch!='\n'; j++)
		{
			T[j] = ch;
			ch = getchar();
		}
		T[0] = j-1;
		pos = Index_KMP(S,T);
		printf("%d\n", pos);
	}
}

void get_next(SString T, int next[])
{
	int i, j;
	
	next[1] = 0;
	i = 1; j = 0;
	while(i<T[0])
	{
		if(j==0 || T[i]==T[j])
		{
			i++; j++;
			next[i] = j;
		}
		else j = next[j];
	}
}

int Index_KMP(SString S, SString T)
{
	int next[MAXSTRLEN];
	int i, j;
	
	get_next(T, next);
	i = 1; j = 1;
	while(i<=S[0] && j<=T[0])
	{
		if(j==0 || S[i]==T[j])
		{
			i++; j++;
		}
		else j = next[j];
	}
	if(j>T[0]) return i-T[0];
	else return 0;
}