kmp算法next数组的求法C语言
时间: 2024-05-11 19:12:20 浏览: 18
KMP算法是一种字符串匹配算法,其核心是利用next数组实现快速定位模式串与主串不匹配时,模式串应该向右移动的位置。下面介绍一下KMP算法中next数组的求法:
假设模式串为P,长度为m。next数组是一个长度为m的数组,其中next[i]表示P中以第i个字符结尾的子串中,最长的既是前缀又是后缀的字符串的长度。例如,当P="ababc"时,next=2,因为以第4个字符'b'结尾的子串"ab"是既是前缀又是后缀的字符串,其长度为2。
next数组的求法可以使用递推的方式进行。首先定义next=-1,next=0,然后从i=2开始,依次计算next[i]:
1. 如果P[next[i-1]]等于P[i-1],则next[i]=next[i-1]+1;
2. 如果P[next[i-1]]不等于P[i-1],则令j=next[next[i-1]],重复执行以下步骤:
a. 如果P[j]等于P[i-1],则next[i]=j+1;
b. 如果j=-1,则next[i]=0,并退出循环;
c. 否则令j=next[j],返回步骤2。
下面是求解next数组的C语言代码示例:
```c
void getNext(char* P, int* next) {
int m = strlen(P);
next = -1;
int i = 0, j = -1;
while (i < m - 1) {
if (j == -1 || P[i] == P[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
```