西安高端网站制作,产品推广软文,免费的源代码分享有哪些网站,上海网络营销公司数据结构—KMP模式匹配病毒感染人的DNA检测
原理#xff1a;参考趣学数据结构
代码#xff1a;
#includestdio.h
#includestdlib.h
#define N 100
int next[N];
void getNext(char *T, int *next, int m) {//求解当前字符前面的最大公共前缀和后缀int j …数据结构—KMP模式匹配病毒感染人的DNA检测
原理参考趣学数据结构
代码
#includestdio.h
#includestdlib.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;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) {//不能在这里使用in-m1,否则可能会破坏截断)匹配成功if (i n - m 1 j 1) {break;//再减少一点比较的次数}if (j 0 || S[i] T[j]) {i;j;}else {j next[j];//根据最大公共前缀和后缀计算的next数组j回退而i不回退}}//printf(\n--- %d ---\n, j);if (j m1) {//返回查找成功子串的初始位置 不能写成 写更安全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 {//对循环重新开始的数取%(m1)再加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);getNext(TT, next, m);//计算next数组最大公共前缀和后缀长度printf(\n);KMP(S, TT, 1, n, m);//模式匹配printf(\n);}
}
int main() {char S[18] -adecadecadcbadcb;char T[10] -adecadcb;//\0字符串结束的标识haveAffectionV(S, T, 16, 8);system(pause);return 0;
}测试截图 彩蛋留一个问题:为什么kmp函数的while条件里面不能写in-m1来降低几次比较
时间复杂度O(m x (mn)),空间复杂度O(m)
如果存在什么问题欢迎批评指正谢谢
