KMP

通过子串寻找规律，计算出 next 数组的值。同时支付串数组0下标依然存储字符串长度。

next 数组

当前元素的前一个元素和一开始的元素相同出现的频次+1。

void get_next(char t[], int next[]){ // t为子字符串 
    int i=1,j=0; // i 记录子字符串的下标位置， j 记录子字符串对比的起始位置
    next[1]=0; // next 第二位 必须是 0
    while(i < t[0]){ // 子字符串的长度
        if( j == 0 || t[i] ==t[j]){ // t[i] ==t[j] 从子字符串中进行对比， j==0 子字符串又重头开始自我比对
            ++i;++j;
            next[i] = j; // next 记录出现重复的位置
        }else{
            j = next[j]; // 不相同时，将子字符串重新移动的位置
        }
    }
}

KMP 比对

借助 next数组实现。

int KMP(char S[],char T[],int next[],int pos)
{
    int i=pos;//开始查找的起始位置
    int j=1;
    while(i<=S[0]&&j<=T[0])
    {
        if(j==0||S[i]==T[j]){//相等各自加加，往后走
            ++i;
            ++j;
        }
        else//不等，就回退next[j]的位置
            j=next[j];
    }
    if(j>T[0])//说明比对成功
        return i-T[0];
    else
        return 0;
}

字符串匹配实例

点击查看

#include <stdio.h>
#include <string.h>

typedef char* SString;

//int Index(SString s,SString t){
int Index(char *s,char *t){ // 同上等效
    int i=1,j=1;
    while(i <= s[0] && j<= t[0]){
        if(s[i] == t[j]){
            ++i,++j; // 继续比较后面的字符
        }else{
            i=i-j+2,j=1; //短字符串回到第一位，长字符串对比位置作相应的回调
        }
    }
    if(j>t[0]){ // 短字符串比较完
        return i-t[0]; //返回比对成功时长字符串的起始位置
    }else{
        return 0; // 短字符串未出现在长字符串中
    }
}

void get_next(char t[], int next[]){ // t为子字符串
    int i=1,j=0; // i 记录子字符串的下标位置， j 记录子字符串对比的起始位置
    next[1]=0; // next 第二位 必须是 0
    while(i < t[0]){ // 子字符串的长度
        if( j == 0 || t[i] ==t[j]){ // t[i] ==t[j] 从子字符串中进行对比， j==0 子字符串又重头开始自我比对
            ++i;++j;
            next[i] = j; // next 记录出现重复的位置
        }else{
            j = next[j]; // 不相同时，将子字符串重新移动的位置
        }
    }
}

int KMP(char S[],char T[],int next[],int pos)
{
    int i=pos;//开始查找的起始位置
    int j=1;
    while(i<=S[0]&&j<=T[0])
    {
        if(j==0||S[i]==T[j]){//相等各自加加，往后走
            ++i;
            ++j;
        }
        else//不等，就回退next[j]的位置
            j=next[j];
    }
    if(j>T[0])//说明比对成功
        return i-T[0];
    else
        return 0;
}

int KMPS(char S[],char T[],int pos=1)
{
    int i=pos;//开始查找的起始位置
    int j=1;
    while(i<=S[0]&&j<=T[0])
    {
        if(j==0||S[i]==T[j]){//相等各自加加，往后走
            ++i;
            ++j;
        }
        else{ //不等时继续往后对比
            i++;
            j=1;
        }

    }
    if(j>T[0])//说明比对成功
        return i-T[0];
    else
        return 0;
}

int main() {
    char S[256],T[10],P[10];
    int next[20];
    int pos;

    S[0]=strlen("abcabaaabaabcac"); // 字符数组第一位存储字符串长度
    strcpy(S+1,"abcabaaabaabcac");// 字符拼接
    T[0]=strlen("abaabc"); // 字符数组第一位存储字符串长度
    strcpy(T+1,"abaabc");// 字符拼接

    pos = Index(S,T); // 暴力匹配
    if(pos){
        printf("匹配成功，位置为长字符串的第%d位。\n",pos);
    }else{
        printf("未匹配到相关内容！\n");
    }

    get_next(T,next);//算出next数组

    pos=KMP(S,T,next,1);
    if(pos){
        printf("匹配成功，位置为长字符串的第%d位。\n",pos);
    }else{
        printf("未匹配到相关内容！\n");
    }

    return 0;
}