模式串匹配算法（朴素模式匹配算法和KMP算法）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 255
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

/**
串的顺序存储和链式存储 
由于C语言中有对串直接操作的函数,这只列举一种操作 
朴素模式匹配算法 
*/

//静态定义串的结构体(定长顺序存储)
typedef struct{
    char ch[MaxSize];//存储字符的数组 
    int length;//串的实际长度 
}SString; 

//动态方式定义串的结构体(为了避免存储密度低的问题,让结点存储多个字符) 
typedef struct StringNode{
    char ch[4];//每个结点放四个字符 
    struct StringNode *next;//指针域 
}StringNode,*String; 

//动态定义串的结构体(堆分配存储)
typedef struct{
    char *ch;//按照串长分配储存区,ch指向串的首地址 
    int length;//串的实际长度
}HString; 

//堆分配初始化
void InitHString(HString &S){
    S.ch = (char*)malloc(MaxSize*sizeof(char));
    S.length = 0;
} 

//求子串
bool SubString(SString &Sub,SString S,int pos,int len){
    //子串越界
    if(pos+len-1>S.length){
        return false;
    } 
    for(int i=pos;i<pos+len;i++){
        Sub.ch[i-pos+1] = S.ch[i];
    }
    Sub.length = len;
    return true;
}

//朴素模式匹配算法 
int Index(SString S,SString T){
    int k=1;
    int i=k,j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            ++i;
            ++j;//继续比较后续字符 
        }else{
            k++;//检查下一个子串 
            i=k;
            j=1;
        }
    }
    if(j>T.length){
        return k;
    }else{
        return 0;
    }
}

//求模式串中next数组
void get_next(SString T,int next[]){
    int i = 0;
    int j = 0;
    next[1] = 0;
    while(i<T.length){
        if(j==0||T.ch[i]==T.ch[j]){
            ++i;
            ++j;
            //若pi=pj,则next[j+1]=next[j]+1 
            next[i] = j;
        }else{
            //否则循环继续 
            j = next[j];
        }
    }
} 

//KMP算法2 
int IndexKMP(SString S,SString T){
    int i=1,j=1;
    int next[T.length+1];
    get_next(T,next);
    while(i<=S.length && j<=T.length){
        if(j==0||S.ch[i]==T.ch[j]){
            ++i;
            ++j;//继续比较后续字符 
        }else{
            j=next[j];//模式串向右移动 
        }
    }
    if(j>T.length){
        return i-T.length;//匹配成功 
    }else{
        return 0;
    }
}

//KMP算法1
int Index(SString S,SString T,int next[]){
    int i=k,j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            ++i;
            ++j;//继续比较后续字符 
        }else{
            j=next[j];
        }
    }
    if(j>T.length){
        return i-T.length;
    }else{
        return 0;
    }
} 

int main(int argc, char** argv) {
    HString S;
    InitHString(S);
    return 0;
}

模式串匹配算法（朴素模式匹配算法和KMP算法）

原文：https://blog.51cto.com/14049943/2609321