数据结构kmp算法代码
时间: 2023-11-14 08:12:14 浏览: 45
这里提供了朴素模式匹配算法的代码实现和KMP算法的相关知识点,但并没有给出KMP算法的代码实现。KMP算法是一种字符串匹配算法,它的核心是求解next数组,通过next数组来避免不必要的比较,提高匹配效率。下面是KMP算法的代码实现:
```
void getNext(string T, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (i < T.length() - 1) {
if (j == -1 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
int KMP(string S, string T, int pos) {
int i = pos, j = 0;
int next[T.length()];
getNext(T, next);
while (i < S.length() && j < T.length()) {
if (j == -1 || S[i] == T[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == T.length()) {
return i - T.length();
} else {
return -1;
}
}
```