#include<stdio.h>
#include<stdio.h>
#pragma warning(disable:4996)
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN + 1];
void strLength(SString S)
{
int m;
for (m = 1; S[m] != '\0'; m++);
S[0] = m - 1;
}
void get_next(SString T, int* next)
{
//求模式T的next函式值并存入陣列next，為后面進行模式匹配做準備
int j, k;
j = 1;
next[1] = -1;
k = -1;//初始值
while (j < T[0])
{
if (k == -1 || T[j] == T[k])
{
++j;++k;
next[j] = k;
}
else k= next[k];
}
}
int Index_KMP(SString S, SString T, int pos, int *next)
{
int i, j;
i = pos;
j = 1;
get_next(T,next);
while (i < S[0] && j < T[0])
{
if (j == -1 || S[i] == T[j])
{
++i;
++j;
}
else j = next[j];
}
if (j >=T[0])
return
i - T[0];
else
return 0;
}
void main()
{
SString S, T;
int pos;
int next[MAXSTRLEN];
int* p = &next[1];
int r;
printf("輸入主串S:");
scanf("%s", S + 1);
printf("輸入模式串T:");
scanf("%s", T + 1);
printf("輸入起始位置pos:");
scanf("%d", &pos);
strLength(S);
strLength(T);
if (r = Index_KMP(S, T, pos, p))
printf("模式串在主串中的位置為:%d\n", r);
else
printf("匹配失敗！");
}
uj5u.com熱心網友回復：
KMP演算法是資料結構的內容，在C語言這里提問，估計沒有人愿意回答。uj5u.com熱心網友回復：
你的next陣列的計數錯誤的因為你這么寫是從0開始計數，但實際上你應該從1開始計數
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30900.html
標籤：C語言
上一篇：c++初學類和物件，報錯no matching function for call to'undergarduate::undergarduate()'
下一篇：檔案的上傳與下載