串 和 KMP算法

串:内容受限的线性表(数据元素只能是字符)

串: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算法
得到前缀表
串 和 KMP算法

KMP过程:

串 和 KMP算法

(匹配正确,匹配字串下一个)

串 和 KMP算法

错误匹配

串 和 KMP算法

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

串 和 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];
        }
    }
}


上一篇:初始cfx开发webservice, 简单实例应用


下一篇:浅谈kmp