串和 KMP算法

2022-01-31 04:59:08

串：内容受限的线性表（数据元素只能是字符）

串：String--- 字符组成的有限序列
顺序储存用的多
案例：病毒感染检测（病毒dna环状）

结构类型定义

#define MAXLEN 255
typedef struct
{
     char ch[MAXLEN+1];
     int length;
}SString;

下面是链串定义

#define CHUNKIZE 80//块大小
typedef struct Chunk //块
{
    char ch[CHUNKIZE];
    struct Chunk *next;
}Chunk;
typedef struct
{
    Chunk *head,*tail;//头指针，尾指针
    int curlen;//串的当前长度
}LString;  //字符串的块链结

串的模式匹配算法

提示：
【如果某串是循环串，将该串连续储存两次，然后再匹配】
算法作用：
确定主串（正文串）所含字串（模式串）第一次出现的位置（定义）

BF算法（暴力）（ O(n*m) ）

简述：

回溯：i={ i - ( j-1 ) } + 1=i-j+1+1
重头开始：j=1；
字串出现位置：POS=i-t.length

代码：
就不解释了，一看就懂

int index_BF(String S,String T,int pos)
//S表示主串（被匹配串），T表示匹配串
//pos表示从主串第pos个位置开始匹配
{
    int i=pos;//i指向主串
    int j=0;//j指向匹配串
    while(i<S.length&&j<T.length)
    {
        if(S.ch[i]==T.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(j>=T.length)
    {
        return i-T.length;
    }
    else return -1;
}

KMP算法

简述：

优点：速度快
- 主串不必回溯：
- 模式串不必重头开始：j=1；
难点：获取next[j]
- next[j]含义：当第 j 个字符与主串中相应的字符“匹配失败”时，模式串重新与主链匹配的位置

图画实现

前期准备：
列出所有公共子序列，求最长公共前后缀

得到前缀表

KMP过程：

（匹配正确，匹配字串下一个）

错误匹配

看前缀表，从前缀表写的位置开始匹配

代码实现

获取next[j]

思想：
只有较长字串比较短字串多的那个字符，是较短字符的最长公共前后缀的前缀的下一个字符，才有较长字串的最长公共前后缀的长度是较短的长度+1；
否则就是和找上一个，直到找到匹配的

代码：

void get_next(String T,int next[])
{
    next[0]=0;
    /*
      作用：初始化
      含义：当串T第一个元素匹配失败后，
        下一次匹配串 T还是从第1格元素开始匹配
    */
    int len=0;
    /*
      len含义：
        前一个的最长公共子序列长度
        即：最后一个元素所在位置
    */
    int i=1;
    /*

      i含义：
      . 正在检测串的第i个字母
    */
      while(i<T.length)
    {
        if(T.ch[i]==T.ch[len])//
        {
            len++;
            next[i]=len;
            i++;
        }
        else
        {
            if(len>0)
            {
          /*aabcd ae aabce 此时len指向d，i指向e
            然后去找前一个最长公共序列长度.*/
                len=next[len-1];
            }
            else
            {
                next[i]=len;//即next[i]=0;
                i++;
            }
        }
    }
    //为了方便运算，向后移一位
    for(i=T.length; i>0; i--)
    {
        next[i]=next[i-1];
    }
    next[0]=-1;
}

index_KMP

void index_KMP(String S,String T,int pos)
{
    int i=pos;
    int j=0;
    int next[T.length];
    get_next(T,next);
    while(i<S.length)
    {
        if(j==T.length-1 && S.ch[i]==T.ch[j])
        {
            printf("%d\n",i-j+1);
            return;
            //j=next[j];
            /*如果不return，就会搜寻下一个符合的*/
        }
        if(j==-1||S.ch[i]==T.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
}

码农公寓