kmp算法完成DNA的病毒感染检测

运行结果：

代码：

#include<cstring>
#include<iostream>

using namespace std;

#define OK 1
#define ERROR 0;
#define OVERFLOW -2
typedef int Status;
#define MAXSTRLEN 255
typedef char SString[MAXSTRLEN + 1];
const int maxn = 100;

Status StrAssign(SString T, char *chars){
? ? //生成一个其值等于chars的串T
? ? int i;
? ? if (strlen(chars) > MAXSTRLEN)
? ? {
? ? ? ? return ERROR;
? ? }
? ? else
? ? {
? ? ? ? T[0] = strlen(chars);
? ? ? ? for (i = 1; i <= T[0]; i++)
? ? ? ? ? ? T[i] = *(chars + i - 1);
? ? ? ? return OK;
? ? }//else
}//StrAssign
void get_next(SString T, int next[]){
? ? //求模式串T的next函数值并存入数组next。
? ? int i = 1;
? ? next[1] = 0;
? ? int j = 0;
? ? while (i < T[0])
? ? {
? ? ? ? if (j == 0 || T[i] == T[j])
? ? ? ? {
? ? ? ? ? ? ++i; ++j; next[i] = j;
? ? ? ? }//if
? ? ? ? else j = next[j];
? ? }//while
}//get_next
int Index_KMP(SString S, SString T, int pos)
{
? ? //利用模式串T的next函数求T在主串S中第pos个字符之后的位置的
? ? //KMP算法。其中，T非空，1<<pos<<StrLength(S).
? ? int i = pos;
? ? int j = 1;
? ? int next[maxn];
? ? get_next(T, next);
? ? while (i <= S[0] && j <= T[0]){
? ? ? ? if (j == 0 || S[i] == T[j]){//继续比较后继字符
? ? ? ? ? ? ++i; ++j;
? ? ? ? }//if
? ? ? ? else j = next[j];//模式串向右移动
? ? }//while
? ? if (j > T[0])
? ? ? ? return i - T[0];//匹配成功
? ? else return 0;
}//Index_KMP

int main()
{
? ? int next[maxn];
? ? char str[maxn], mo[maxn];
? ? SString S, T;

? ? cout << "请输入DNA序列" << endl;
? ? cin >> mo;
? ? cout << "请输入病毒序列" << endl;
? ? cin >> str;
? ? StrAssign(S, mo);
? ? StrAssign(T, str);
? ? next[0] = -1;
? ? get_next(T,next);
? ? //printf("%d\n", Index_KMP(S,T,0));
? ? cout << "病毒在DNA在第" << Index_KMP(S, T, 1) << "个结点处首次匹配\n";
? ? return 0;

}

kmp算法完成DNA的病毒感染检测

原文：https://blog.51cto.com/u_15098794/2973858