串和KMP算法

2021-11-15 05:56:44

一、串

串是由零个或多个字符串组成的有限序列

（一）、串的定义

定长顺序存储

  1. 特点:每个串变量分配一个固定长度的存储区,即定长数组

  2. 定义:

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

堆分配存储表示

这里的堆是指c语言中存在一个称之为"堆"的*存储区，这里的堆是一个链表的结构,和数据结构中的堆是不同的!

  1. 特定:存储空间在程序执行过程中动态分配

  2. 定义

    typedef struct{
    char *ch;
    int length;
}HString;

块链存储表示

  1. 特点:使用链表结构,每个节点可以存储4个字符

（二）、最小操作集

  1. 串赋值
  2. 串比较
  3. 求串长
  4. 串联结
  5. 求子串

二、串的模式匹配

模式匹配:子串的定位操作

（一）、简单的模式匹配算法

  1. 定义:暴力匹配算法

  2. 功能:在主串s1中查找子串s2,如果找得到就返回位置(下标+1),否则返回-1

  3. 思路:以在主串abababc中匹配子串abc为例

    设i为当前匹配主串的位置,j为匹配子串的位置

    • 匹配s1[i]是否等于s2[j],相等到第二步,不相等则到第三步
    • 相等,i++,j++
    • 不相等,使i=i-j+1,j==0,倒退重新匹配
    • 重复以上操作,直到i==strlen(s1)或j==strlen(s2)

  4. code

    #include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int cmp(string s1,string s2){  //s1主串,s1子串
    int ans,i=0,j=0,len1=s1.length(),len2=s2.length();
    while(i<len1&&j<len2){  //注意len与下标差1
        //cout << "i:" << i << " j:" << j << endl;
        if(s1[i]==s2[j]){
            i++,j++;
        }else{
            i=i-j+1;  //上一个匹配初始位的下一个pos
            j=0;
        }
    }
    ans=j==len2?i-j:-1;
    return ans+1;  //注意pos是下标位置,下标->位置
}

int main(){
    string s1,s2;
    cin >> s1 >> s2;
    int pos = cmp(s1,s2);
    printf("pos:%d\n",pos);
}

  5. 时间复杂度:O(m*n)(设strlen(s1)=n,strlen(s2)=m)

  6. 主要存在的问题:

    • 显然s1至少要匹配n-m+1次
    • 我们可以想办法通过空间换时间的方式减少s2的匹配次数(即想办法膜除第三步中回退的过程)

（二）、KMP算法

解决暴力匹配过程中回退的问题

相关概念

  1. 前缀:除最后一个字符,字符串的所有头部子串
  2. 后缀:除第一个字符外,字符串的所有尾部子串
  3. 部分匹配:字符串的前缀和后缀的最长相等前后缀长度

具体操作

  1. 列出最长相等前后缀长度

    以待匹配字符串ababa为例

    序号 子字符串 前缀 后缀 最长相等前后缀长度
    1 a 0
    2 ab b a 0
    3 aba a,ab ba,a 1
    4 abab a,ab,aba bab,ab,b 2
    5 ababa a,ab,aba,abab baba,aba,ba,a 3

  2. 构建部分匹配值表(Partial Match)

    编号 1 2 3 4 5
    s a b a b a
    pm(上表最后一列) 0 0 1 2 3

  3. 使用(为了方便理解算法,我们这里用1作为下标起点)

    操作:

    • 匹配s1[i]是否等于s2[j]

    • 相等,i++,j++

    • 不相等,j=j-(j-1-pm[j-1]),即使子串回退

      回退的距离move=已匹配的字符数-对应的部分匹配值=j-1-pm[j-1]

    • 重复以上操作,直到i>=strlen(s1)或j>=strlen(s2)

    如:

    s1:abacdababa

    s2:ababa

    • 当i=4,j=4,显然s1[i]!=s2[j]
    • j=4-(4-1-pm[4-1])=2,i不需要回退

  4. 优化pm表

    • 存在问题:

      • pm[5]对应第6个字符匹配失败,显然是用不到的

      优化:将pm表整体右移一格构成一张新表称为next,表示子串下一个应该匹配的位置,使next[1]=-1

      编号 1 2 3 4 5
      s a b a b a
      next -1 0 0 1 2

      此时:

      move=j-1-next[j]

      j=j-move=j-(j-1-next[j])=next[j]+1

      注:关于这里使用-1,王道给出的解释是"因为若是第一个元素匹配失败,则需要将子串向右移动一位,而不需要计算子串移动的位数",简单来说就是此时只要将主串左移,不需要move.(我靠,NewBee,写到这里突然悟了!!小黄鸭原理可以的.)

    • 继续改进:显然,我们可以之际在next[j]上加1出

      编号 1 2 3 4 5
      s a b a b a
      next 0 1 1 2 3

      注:(这里再备注一下next下标的意义)

      • next[i]=0,表示没有一个前缀可以匹配,主要作为标识符使用
      • next[i]=j],j表示有i个前缀可以匹配

      此时:

      move=next[j]

      j=next[j]

推理next数组的一般公式

  1. next函数的一般公式(设首位下标为1):

    • next[j]=0,j=1(即第一位不匹配时需要移动)
    • next[j]=max{k|1<k<j且\(`P_1...P_{k-1}`=`P_{j-k+1}...P_{j-1}`\)}
    • 1,其它

  2. 尝试通过已知next[j]推导next[j+1]:

    令k=next[j],s2为子串

    • k=0,则next[j+1]=next[j]+1
    • s2[j]=s2[k],则next[j+1]=next[j]+1
    • s2[j]!=s2[k],则k=next[k],继续循环匹配

编写代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

string s1,s2;
int nextValue[N];

void getNext(string s,int *nextValue){
    int now=1,k=0,len=s.length();
    nextValue[0]=-1;  //设定nextValue[0]=-1,作为一个特殊的标识符表示第一个值没有匹配到
    while(now<len){
        if(k==-1){  //递归出口
            nextValue[++now]=++k;
            continue;
        }
        if(s[now]==s[k]){  //递归体
            nextValue[++now]=++k;
        }else{
            k=nextValue[k];
        }
    }
}

//找得到返回第一次出现的pos,否则返回-1
int kmpCmp(string s1,string s2){
    int i=0,j=0,ans=-1;
    int len1=s1.length(),len2=s2.length();
    while(i<len1&&j<len2){
        if(j==-1||s1[i]==s2[j]){
            i++;
            j++;
        }else{
            j=nextValue[j];
        }
    }
    if(j==len2){
        ans=i-len2+1;
    }
    return ans;
}

int main()
{
    cin >> s1;
    cin >> s2;
    getNext(s2,nextValue);
    cout << kmpCmp(s1,s2);
    return 0;
}

注:感觉在局部有点问题,没有找到好的测试样例

优化

  1. 问题产生:显然当s1[i]!=s2[j]时,我们会置换j=next[j].而当s1[i]!=s2[j],j=next[j]时,显然s1[i]!=s2[next[j]],这是一次失效的匹配

  2. 解决:当我们在创建next数组时,我们可以先判断,再通过next[j]=[next[j]]来消除这一情况(记住,这一过程是近似递归的!)

  3. 代码

    #include <bits/stdc++.h>

using namespace std;

const int N=1e5+10;

string s1,s2;
int nextValue[N];

void getNext(string s,int *nextValue){
    int now=1,k=0,len=s.length();
    nextValue[0]=-1;  //设定nextValue[0]=-1,作为一个特殊的标识符表示第一个值没有匹配到
    while(now<len){
        if(k==-1){  //递归出口
            nextValue[++now]=++k;
            continue;
        }
        if(s[now]==s[k]){  //递归体
            nextValue[++now]=++k;
        }else{
            k=nextValue[k];
        }
    }
}

//找得到返回第一次出现的pos,否则返回-1
int kmpCmp(string s1,string s2){
    int i=0,j=0,ans=-1;
    int len1=s1.length(),len2=s2.length();
    while(j<len2){
        if(j==-1||s1[i]==s2[j]){
            i++;
            j++;
        }else{
            if(s1[j]!=s1[nextValue[j]]){
                j=nextValue[j];
            }else{
                j=nextValue[nextValue[j]];
            }
        }
    }
    if(j==len2){
        ans=i-len2+1;
    }
    return ans;
}

int main()
{
    cin >> s1;
    cin >> s2;
    getNext(s2,nextValue);
    cout << kmpCmp(s1,s2);
    return 0;
}
上一篇：NSUOJ2877 KMP裸题（字符串哈希或kmp）


下一篇：模式匹配BF算法和KMP算法