C++ 中KMP字符串匹配算法

//============================================================================
// Name : KMP.C
// Author : ruochenchen http://yige.org/cpp/
// Created on : 2012-11-01
// Copyright : Your copyright notice
// Compiler : VS2010
// Language : C/C++
// Description : KMP字符串匹配算法
//============================================================================
//-----------串的结构采用《数据结构》吴伟民版对于串定长顺序的描述
//-----------串的定长顺序储存结构-------------------
#define MAXSTRLEN 255 //最大串长
typedef unsigned char SString[MAXSTRLEN + 1]; //0号单元存放串的长度 
int next[20];
//-----------串的定长顺序储存结构-------------------
//-----------基本操作------------------
int StrAssign(SString S, char * chars);
//初始条件：
//操作结果：生成一个其值等于串常量chars的串S
int StrLength(SString S);
//初始条件：串S存在
//操作结果：返回S的元素个数。
int StrAssign(SString S, char * chars) {
    int i = 0,
    j = 1;

    while (chars[i] != '\0' && j <= MAXSTRLEN) {
        S[j] = chars[i];
        j++;
        i++;
    }
    if (chars[i] != '\0') {
        return - 1;
    }
    S[j] = '\0';
    //S[0]=StrLength(S);
}

int StrLength(SString S) {
    int i = 1,
    count = 0;
    while (S[i] != '\0') {
        count++;
        i++;
    }
    return count;
}
//-----------基本操作------------------

#include < stdio.h > #include < string.h > void get_next(SString T, int next[]);
void get_next(SString T, int next[]) { //求模式串T的next函数值并存入数组next。
    int i = 1,
    j = 0;
    next[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[j] == T[i]) {++i; ++j;
            next[i] = j;
        } else j = next[j];
    }
}
int Index_KMP(SString S, SString T, int Pos) {
    int i = Pos,
    j = 1;
    int sl,
    tl;
    sl = StrLength(S);
    tl = StrLength(T);
    while (i <= sl && j <= tl) {
        if (j == 0 || S[i] == T[j]) {++i; ++j;
        } else {
            j = next[j];
        }
    }
    if (j > tl) {
        printf("匹配成功");
        return i - tl;
    } else printf("无法匹配模式");
}

//----------主函数
void main() {
    SString S,
    T;
    char Tstr[20];
    int seat;
    char Str[] = "TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT"; //匹配的文本序列
    StrAssign(S, Str);
    printf("请输入模式字符串:\n");
    scanf("%s", Tstr);
    StrAssign(T, Tstr);
    get_next(T, next);
    seat = Index_KMP(S, T, 1);
    printf("在第%d个位置匹配", seat)
}

相关文章

• c/c++编译笔记 2012/11/07