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

运行结果:

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、Rabin-Karp算法)


下一篇:KMP的一些好题