數(shù)據(jù)結(jié)構(gòu)—KMP模式匹配病毒感染人的DNA檢測

原理：參考趣學(xué)數(shù)據(jù)結(jié)構(gòu)

代碼：

#include<stdio.h> #include<stdlib.h> #define N 100 int next[N]; void getNext(char *T, int *next, int m) {//求解當(dāng)前字符前面的最大公共前綴和后綴int j = 1, k = 0;next[j] = 0;//從1開始計(jì)算while (j <= m) {if (k == 0 || T[k] == T[j]) {//從下標(biāo)0開始計(jì)算++j;++k;if (T[k] == T[j]) {//改進(jìn)的更新next數(shù)組的方法，減少不必要的回退next[j] = next[k];//沒比較的可能}else {//也就是只有不相等的時(shí)候才有比較的可能next[j]=k;//與當(dāng)前k位置的字符比較}}else {k = next[k];//回退查找前面的最大公共前綴和后綴}}printf("next數(shù)組值:");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算法進(jìn)行模式匹配int i = pos, j = 1;while (i <= n&& j <= m) {//不能在這里使用i<=n-m+1,否則可能會(huì)破壞（截?cái)?匹配成功if (i > n - m + 1 && j == 1) {break;//再減少一點(diǎn)比較的次數(shù)}if (j == 0 || S[i] == T[j]) {i++;j++;}else {j = next[j];//根據(jù)最大公共前綴和后綴計(jì)算的next數(shù)組，j回退而i不回退}}//printf("\n--- %d ---\n", j);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];//存儲(chǔ)病毒的變種 m個(gè)變種,不采用二倍線性擴(kuò)展變種，使用循環(huán)取余變種for (int i = 0; i <= m-1; i++) {//移動(dòng)的步數(shù)for (int j = 1; j <= m; j++) {if (i + j <= m) {TT[j] = T[i + j];}else {//對循環(huán)重新開始的數(shù)取%(m+1)再加1對應(yīng)下標(biāo)的字符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);//計(jì)算next數(shù)組（最大公共前綴和后綴長度）printf("\n");KMP(S, TT, 1, n, m);//模式匹配printf("\n");} } int main() {char S[18] = "-adecadecadcbadcb";char T[10] = "-adecadcb";//'\0'字符串結(jié)束的標(biāo)識(shí)haveAffectionV(S, T, 16, 8);system("pause");return 0; }

測試截圖：

彩蛋：留一個(gè)問題:為什么kmp函數(shù)的while條件里面不能寫i<=n-m+1來降低幾次比較？？？

時(shí)間復(fù)雜度O(m x (m+n)),空間復(fù)雜度O(m)

如果存在什么問題！歡迎批評指正！謝謝！

總結(jié)

以上是生活随笔為你收集整理的数据结构---KMP模式匹配病毒感染人的DNA检测的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。