数据结构—KMP模式匹配病毒感染人的DNA检测
原理:参考趣学数据结构
代码:
#include<stdio.h>
#include<stdlib.h>
#define N 100
int next[N];
void getNext(char *T, int *next, int m) {//求解当前字符前面的最大公共前缀和后缀
int j = 1, k = 0;
next[j] = 0;//从1开始计算
while (j <= m) {
if (k == 0 || T[k] == T[j]) {//从下标0开始计算
++j;
++k;
next[j] = k;
/*if (T[k] == T[j]) {//改进的更新next数组的方法,减少不必要的回退
next[j] = next[k];//没比较的可能
}
else {//也就是只有不相等的时候才有比较的可能
next[j]=k;//与当前k位置的字符比较
}*/
}
else {
k = next[k];//回退查找前面的最大公共前缀和后缀
}
}
printf("next数组值:");
for (int i = 1; i <= m; i++) {
printf("%d ", next[i]);
}
printf("\n");
}
int KMP(char * S, char* T, int pos, int n, int m) {//KMP算法进行模式匹配
int i = pos, j = 1;
while (i <= n && j <= m) {
if (j == 0 || S[i] == T[j]) {
i++;
j++;
}
else {
j = next[j];//根据最大公共前缀和后缀计算的next数组,j回退而i不回退
}
}
if (j = m + 1) {//返回查找成功子串的初始位置
printf("查找成功子串的初始位置为:%d\n", i - j);
return i - j;
}
printf("查找子串失败!\n");
return -1;
}
void haveAffectionV(char *S,char* T,int n,int m) {//检查人的DNA是否被病毒的变种感染
char TT[10];//存储病毒的变种 m个变种,不采用二倍线性扩展变种,使用循环取余变种
for (int i = 0; i <= m-1; i++) {//移动的步数
for (int j = 1; j <= m; j++) {
if (i + j <= m) {
TT[j] = T[i + j];
}
else {//对循环重新开始的数取%(m+1)再加1对应下标的字符
TT[j] = T[(i + j) % (m + 1)+1];
}
}
for (int k = 1; k <= n; k++) {//遍历主串
printf("%c", S[k]);
}
printf("\n");
for (int k = 1; k <= m; k++) {//遍历子串
printf("%c", TT[k]);
}
printf("\n");
KMP(S, TT, 1, n, m);//模式匹配
printf("\n");
}
}
int main() {
char S[18] = "-adecadecadcbadcb";
char T[10] = "-adecadcb";//'\0'字符串结束的标识
getNext(T, next, 8);//计算next数组(最大公共前缀和后缀长度)
printf("\n");
haveAffectionV(S, T, 16, 8);
system("pause");
return 0;
}
测试截图:
![数据结构---KMP模式匹配病毒感染人的DNA检测 数据结构---KMP模式匹配病毒感染人的DNA检测](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPTcyNGE5ZjI5OTJkNDQxYjI4MmY5YmJhYTNmOTRjM2FmLnBuZz8sdHlwZV9aSEp2YVdSellXNXpabUZzYkdKaFkycyxzaGFkb3dfNTAsdGV4dF9RMU5FVGlCQVptbG5hSFJwYm1mbm1vVG5vSUhsaHB3PSxzaXplXzExLGNvbG9yX0ZGRkZGRix0XzcwLGdfc2UseF8xNg==)
时间复杂度O(m x (m+n)),空间复杂度O(m)
如果存在什么问题!欢迎批评指正!谢谢!