数据结构与算法丨串 2-阿里云开发者社区

三、串的模式匹配

1. 概念

本节重点讨论串定位操作——模式匹配的实现算法。对串的同一种运算，在不同的存储结构上实现时其算法是不同的。由于采用链式存储时其操作与线性链表类似，并且占用的存储空间多，在大多数情况下，串值的存储采用顺序存储方式。

串的模式匹配index(s,t,start)即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置；否则，匹配失败，返回0。子串t称为模式串。

2. 模式匹配的基本算法（BF 算法）

实现模式匹配的最简单、直观的方法是基于蛮力法技术设计的算法，即BF算法。该算法的基本思想是，按照自左至右的顺序，从主串的第start个字符起和模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的第start+1个字符起重新和模式串的字符比较。以此类推，直到模式串t中的每个字符依次和主串s中的一个连续的字符序列相等，则匹配成功；否则，匹配不成功。对应的BF算法代码如下：

int indexBF(SqString *s,SqString *t,int start){
  int i=start-1,j=0;
  while(i<s->length&&j<t->length){
    if(s->data[i]==t->data[j]){
      i++;
      j++;
    }else{
      i=i-j+1;
      j=0;
    }
  }
  if(j>=t->length)
      return i-t->length+1;
  else
      return 0;
}

3. KMP 算法

采用KMP算法的模式匹配过程可分为两个部分，首先对模式串t的每个字符计算其对应的k值，并保存在一个数组next中；然后利用next数组进行模式匹配。

3.1 next 数组

next数组具有如下性质：

（1）next[ j ]是一个整数，且0<=next[ j ]<j。

（2）为了使t的右移不丢失任何匹配成功的可能，当存在多个满足式的k值时，应取最大值，这样向右“滑动”的距离最短，“滑动”的字符为j-next[ j ]个。

next数组的计算 :

void getNext(SqString *t,int next[]){
  int i=0,j=-1;
  next[0]=-1;
  while(i<t->length){
    if((j==-1)||(t->data[i]==t->data[j])){
      i++;
      j++;
      next[i]=j;
    }
    else{
      j=next[j];
    }
  }
}

3.2 KMP 算法

在求得模式的next数组之后，模式匹配过程为，假设以指针i和j分别指示主串和模式中的字符比较位置，令i从start开始，j的初值为1.在匹配过程中，若 si = tj ，则 i 和 j 分别增加1，继续下一个对应位置字符的比较；若 si != tj ，则 i 不变，j 退到next[ j ]位置进行下一趟比较，以此类推。直至下列两种情况：一是 j 退到某个next值时字符比较相等，则i和j分别增加1继续本趟匹配；二是 j 退到值为零（即模式的第一个字符失配），则此时 i 和 j 也要分别增1，表明从主串的下一个字符起和模式重新开始下一趟匹配。直到主串中存在一个连续的字符序列与模式串相同，则匹配成功；否则，匹配失败。

KMP算法：

int indexKmp(SqString *s,SqString *t,int start,int next[]){
  int i=start-1,j=0;
  while(i<s->length&&j<t->length){
    if(j==-1||s->data[i]==t->data[j]);  //s和t对应字符相等，比较下一个字符
    i++;
    j++;
  }
  else j=next[j];      //开始下一次匹配，子串指针j移动到下一个比较位置
  if(j>=t->length+1)
      return(i-t->length+1);
  else
      return 0;
}

4. Horspool 算法

4.1 概念

Horspool算法进行模式匹配的每一趟，总是从模式串的最后一个字符开始与主串中的对应位置的字符进行比较，如果发生字符失配，则需要将模式串整体右移。在不错过匹配机会的前提下，总希望移动的幅度尽可能大。

假设对齐模式串最后一个字符的主串字符是c，Horspool算法根据c的不同情况来确定模式的移动距离。一般可能出现以下4种情况：

（1）如果模式串中不存在字符c，则模式串安全移动的距离就是模式串的长度。

（2）如果模式串中存在字符c，但它不是模式串的最后一个字符，则应将模式串中最右边的c与主串中的c对其。

（3）如果c正好是模式串的最后一个字符，但模式串的其他字符中不包含c，模式串的移动方法类似于情况（1），移动的距离就是模式串的长度。

（4）如果c正好是模式串的最后一个字符，且模式串的其他字符中也包含c，模式串的移动方法类似于情况（2），应将模式串中最右边的c与主串中的c对齐。

因此，类似于KMP算法，可以预先计算每次移动的距离并保存在一个字符移动表中，就可以在模式匹配时利用它确定下一趟匹配的模式串移动距离。

4.2 Horspool 算法

Horspool 算法：

int horspoolMathing(SqString *pat,SqString *txt,int table[]){
  int i=pat->length-1,k;
  while(i<=txt->length-1){
    k=0;
    while((k<=pat->length-1)&&(pat->data[pat->length-1-k]==txt->data[i-k])){
        k++;
    }
    if(k==pat->length) return i-pat->length+1;
    else i=i+table[txt->data[i]];
  }
  return -1;
}

字符移动表的计算：

int shift_table(SqString *pat,int table[]){
  int i,j;
  for(i=0;i<N;i++){
    table[i]=pat->length;
  }
  for(j=0;j<pat->length-1;j++){
    table[pat->data[j]]=pat->length-1-j;
  }
  return 0;
}

四、串的插入

1. 问题引入

给定顺序串S1和S2，编写算法将串S2插入串S1的第 i 个字符前。

2. 思路探析

2.1 借助辅助串

可利用顺序串的方式实现。原理是，分别创建串S1和S2，然后借助一个临时串进行插入。在设计算法时，首先将串S1中指定插入位置后的所有字符复制到临时串中，其次将串S2复制到S1的指定位置上，最后将临时串中的所有字符接到S1串中即完成插入。

具体算法代码如下：

int strInsertSub(SqString *s1,SqString *s2,int pos){
    SqString *s;
    initString(s);
    if(pos<1||pos>s1->length){
        return 0;
    }
    int i,j,t;
    for(i=0,j=pos-1;j<s1->length;i++,j++){
           s->data[i]=s1->data[j];
           s->length++;
    }
    s->data[i]='\0';
    for(i=pos-1,j=0;j<s2->length;i++,j++){
           s1->data[i]=s2->data[j];
    }
    s1->data[i]='\0';
    t=pos-1+strlen(s2->data);
    for(i=t,j=0;j<s->length;i++,j++){
        s1->data[i]=s->data[j];
    }
    s1->data[i]='\0';
    return 1;
}

2.2 直接在S1中操作

可以利用循环，从后往前边判断边插入，这样节省了一个辅助串的空间。

int strInsertSub(SqString *s1,SqString *s2,int pos){
    SqString *s;
    initString(s);
    if(pos<1||pos>s1->length){
        return 0;
    }
    int i=s1->length+s2->length;
    int t=pos-1;
    s1->data[i]='\0';
    while(i>=t){
        s1->data[i]=i>=t+s2->length?s1->data[i-s2->length]:s2->data[i-t];
        i--;
    }
    return 1;
}

3. 具体问题

【问题描述】

已有串s1和s2，利用串的基本操作实现将子串s2插入到主串s1的第i个位置。(串长不超过100)

【输入形式】

第一行输入n，表示有n组数据;

每组数据包括：

输入串s1;

输入串s2;

输入i，表示子串插入到主串中的位置。

【输出形式】

第一行输出两个字符串比较结果：s1与s2中的大者，如果相等则输出equal；

第二行输出插入结果：如果插入操作正确完成则输出插入子串后的主串，否则输出error。

【样例输入】

3

ABCDEFG

%*

2

ABCD

4

1234567890

abc

40

【样例输出】

ABCDEFG

A%*BCDEFG

equal

ABCABCDD

abc

error

3.1 方法一（辅助串）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef struct{
    char *data;
    int length;
    int stringsize;
}SqString;
//初始化
int initString(SqString *s){
    s->data=(char *)malloc(sizeof(char));
    if(!s->data) return 0;  
    s->length=0;
    s->stringsize=MAXSIZE;
    return 1;
}
//将字符串str赋值到串s中
int strAssign(SqString *s, char *str )
{
      int i=0;
      while(*str){
          s->data[i++]=*str++;
    }
    s->data[i]='\0';
    s->length=i;
    return 1;
}
//串比较
int strCompare(SqString *s,SqString *t){
      int i;
      for(i=0;i<s->length&&i<t->length;i++){
          if(s->data[i]!=t->data[i]){
              return s->data[i]-t->data[i];
        }
    }
    return s->length-t->length;
}
//在s中从pos开始取len长度的子串到sub中
int subString(SqString *sub,SqString *s,int pos,int len){
      int i,j=0;
      if(pos<1||pos>s->length||len<0||len>s->length-pos+1){
          return 0;
    }
    for(i=pos-1;i<pos-1+len;i++){
        sub->data[j++]=s->data[i];
    }
    sub->data[j]='\0';
    sub->length=j;
    return 1;
}
//将s1与s2连接到s中
int strConcat(SqString *s,SqString *s1, SqString *s2){
      int i=0,j=0;
      while(s1->length+s2->length>=s->stringsize){
          s->data=(char *)realloc(s->data,(s->stringsize+MAXSIZE)*sizeof(char));
          if(!s->data)   return 0;
          s->stringsize+=MAXSIZE;
    }
      while(i<s1->length){
          s->data[i]=s1->data[i++];
    }
    while(j<s2->length){
        s->data[i++]=s2->data[j++];
    }
    s->data[i]='\0';
    s->length=i;
    return 1;
}
//在s1中指定位置pos插入子串s2
int strInsertSub(SqString *s1,SqString *s2,int pos){
    SqString *s;
    initString(s);
    if(pos<1||pos>s1->length){
        return 0;
    }
    int i,j,t;
    for(i=0,j=pos-1;j<s1->length;i++,j++){
           s->data[i]=s1->data[j];
           s->length++;
    }
    s->data[i]='\0';
    for(i=pos-1,j=0;j<s2->length;i++,j++){
           s1->data[i]=s2->data[j];
    }
    s1->data[i]='\0';
    t=pos-1+strlen(s2->data);
    for(i=t,j=0;j<s->length;i++,j++){
        s1->data[i]=s->data[j];
    }
    s1->data[i]='\0';
    return 1;
}
int main(){
    SqString s1,s2;
    int pos,n,r;
    char str[MAXSIZE];
    initString(&s1);
    initString(&s2);
    scanf("%d",&n);
    while(n--){
        getchar();
        gets(str);
        strAssign(&s1,str);
        gets(str);
        strAssign(&s2,str);
        scanf("%d",&pos);
        r=strCompare(&s1,&s2);
        if(r>0)
                puts(s1.data);
        else if(r<0)
                puts(s2.data);
              else
                printf("equal\n");
        if(strInsertSub(&s1,&s2,pos))
            puts(s1.data);
        else
            printf("error\n");
    }
    return 0;
}

3.2 方法二（直接操作）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef struct{
    char *data;
    int length;
    int stringsize;
}SqString;
//初始化
int initString(SqString *s){
    s->data=(char *)malloc(sizeof(char));
    if(!s->data) return 0;  
    s->length=0;
    s->stringsize=MAXSIZE;
    return 1;
}
//将字符串str赋值到串s中
int strAssign(SqString *s, char *str )
{
      int i=0;
      while(*str){
          s->data[i++]=*str++;
    }
    s->data[i]='\0';
    s->length=i;
    return 1;
}
//串比较
int strCompare(SqString *s,SqString *t){
      int i;
      for(i=0;i<s->length&&i<t->length;i++){
          if(s->data[i]!=t->data[i]){
              return s->data[i]-t->data[i];
        }
    }
    return s->length-t->length;
}
//在s中从pos开始取len长度的子串到sub中
int subString(SqString *sub,SqString *s,int pos,int len){
      int i,j=0;
      if(pos<1||pos>s->length||len<0||len>s->length-pos+1){
          return 0;
    }
    for(i=pos-1;i<pos-1+len;i++){
        sub->data[j++]=s->data[i];
    }
    sub->data[j]='\0';
    sub->length=j;
    return 1;
}
//将s1与s2连接到s中
int strConcat(SqString *s,SqString *s1, SqString *s2){
      int i=0,j=0;
      while(s1->length+s2->length>=s->stringsize){
          s->data=(char *)realloc(s->data,(s->stringsize+MAXSIZE)*sizeof(char));
          if(!s->data)   return 0;
          s->stringsize+=MAXSIZE;
    }
      while(i<s1->length){
          s->data[i]=s1->data[i++];
    }
    while(j<s2->length){
        s->data[i++]=s2->data[j++];
    }
    s->data[i]='\0';
    s->length=i;
    return 1;
}
//在s1中指定位置pos插入子串s2
int strInsertSub(SqString *s1,SqString *s2,int pos){
    SqString *s;
    initString(s);
    if(pos<1||pos>s1->length){
        return 0;
    }
    int i=s1->length+s2->length;
    int t=pos-1;
    s1->data[i]='\0';
    while(i>=t){
        s1->data[i]=i>=t+s2->length?s1->data[i-s2->length]:s2->data[i-t];
        i--;
    }
    return 1;
}
int main(){
    SqString s1,s2;
    int pos,n,r;
    char str[MAXSIZE];
    initString(&s1);
    initString(&s2);
    scanf("%d",&n);
    while(n--){
        getchar();
        gets(str);
        strAssign(&s1,str);
        gets(str);
        strAssign(&s2,str);
        scanf("%d",&pos);
        r=strCompare(&s1,&s2);
        if(r>0)
                puts(s1.data);
        else if(r<0)
                puts(s2.data);
              else
                printf("equal\n");
        if(strInsertSub(&s1,&s2,pos))
            puts(s1.data);
        else
            printf("error\n");
    }
    return 0;
}

五、串的修改

1. 问题引入

编写算法，用串 s3 替换串 s1 中存在的所有特定子串s2

2. 思路探析

可以利用串的删除与串的插入两个基本操作进行修改

2.1 串的删除

我们先写一个在主串中删除子串的算法：（这里要用到BF模式匹配）

int deletes(Pstack s1,Pstack s2){
    int pos,i,j;
    pos=bf(s1,s2,0);
    for(i=0;i<s2->length;i++){
        for(j=pos-1;j<s1->length;j++){
            s1->data[j]=s1->data[j+1];
        }
        s1->length--;
    }
    return 1;
}

2.2 串的插入

我们再写一个在主串中指定位置插入子串的算法：

int insert(Pstack s1,Pstack s2,int pos){
    if(pos<0||pos>s1->length){
        return 0;
    }
    int i=s1->length+s2->length;
    if(i>=s1->size){
        s1->data=(char *)realloc(s1->data,(s1->size+MAX)*sizeof(char));
        if(!s1->data) return 0;
        s1->size+=MAX;
    }
    while(i>=pos){
        s1->data[i]=i>=pos+s2->length?s1->data[i-s2->length]:s2->data[i-pos];
        i--;
    }
    return 1;
}

2.3 串的修改

最后我们通过运用一次穿的删除和一次串的插入即可完成对串的修改操作：

int change(Pstack s1,Pstack s2,Pstack s3){
    int pos;
    pos=bf(s1,s2,0);
    if(pos<1||pos>s1->length) return 0;
    deletes(s1,s2);
    insert(s1,s3,pos-1);
    return 1;
}

3. 具体实现

完整代码如下：

#include<stdio.h>
#include<malloc.h>
#define MAX 100
typedef struct Stack{
    char *data;
    int length;
    int size;
}stack,*Pstack;
int initstack(Pstack s){
    s->data=(char *)malloc(sizeof(char));
    s->length=0;
    s->size=MAX;
    return 1;
}
int strAssign(Pstack s,char *a){
    int i=0;
    while(*a){
        s->data[i++]=*a++;
    }
    s->data[i]='\0';
    s->length=i;
    return 1;
}
int print(Pstack s){
    int i=0;
    while(s->data[i]!='\0'){
        printf("%c",s->data[i]);
        i++;
    }
    return 1;
}
int insert(Pstack s1,Pstack s2,int pos){
    if(pos<0||pos>s1->length){
        return 0;
    }
    int i=s1->length+s2->length;
    if(i>=s1->size){
        s1->data=(char *)realloc(s1->data,(s1->size+MAX)*sizeof(char));
        if(!s1->data) return 0;
        s1->size+=MAX;
    }
    while(i>=pos){
        s1->data[i]=i>=pos+s2->length?s1->data[i-s2->length]:s2->data[i-pos];
        i--;
    }
    return 1;
}
int bf(Pstack s1,Pstack s2,int start){
    int i=start-1,j=0;
    while(i<s1->length&&j<s2->length){
        if(s1->data[i]==s2->data[j]){
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    if(j>=s2->length){
        return i-j+1;
    }else{
        return 0;
    }
}
int deletes(Pstack s1,Pstack s2){
    int pos,i,j;
    pos=bf(s1,s2,0);
    for(i=0;i<s2->length;i++){
        for(j=pos-1;j<s1->length;j++){
            s1->data[j]=s1->data[j+1];
        }
        s1->length--;
    }
    return 1;
}
int change(Pstack s1,Pstack s2,Pstack s3){
    int pos;
    pos=bf(s1,s2,0);
    if(pos<1||pos>s1->length) return 0;
    deletes(s1,s2);
    insert(s1,s3,pos-1);
    return 1;
}
int main(){
    char a[100],b[100],c[100];
    stack s1,s2,s3;
    initstack(&s1);
    initstack(&s2);
    initstack(&s3);
    scanf("%s",a);
    scanf("%s",b);
    scanf("%s",c);
    strAssign(&s2,b);
    strAssign(&s1,a);
    strAssign(&s3,c);
    change(&s1,&s2,&s3);
    puts(s1.data);
    return 0;
}

数据结构与算法丨串 2

三、串的模式匹配

1. 概念

2. 模式匹配的基本算法（BF 算法）

3. KMP 算法

3.1 next 数组

3.2 KMP 算法

4. Horspool 算法

4.1 概念

4.2 Horspool 算法

四、串的插入

1. 问题引入

2. 思路探析

2.1 借助辅助串

2.2 直接在S1中操作

3. 具体问题

3.1 方法一（辅助串）

3.2 方法二（直接操作）

五、串的修改

1. 问题引入

2. 思路探析

2.1 串的删除

2.2 串的插入

2.3 串的修改

3. 具体实现

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构与算法丨串 2

三、串的模式匹配

1. 概念

2. 模式匹配的基本算法（BF 算法）

3. KMP 算法

3.1 next 数组

3.2 KMP 算法

4. Horspool 算法

4.1 概念

4.2 Horspool 算法

四、串的插入

1. 问题引入

2. 思路探析

2.1 借助辅助串

2.2 直接在S1中操作

3. 具体问题

3.1 方法一（辅助串）

3.2 方法二（直接操作）

五、串的修改

1. 问题引入

2. 思路探析

2.1 串的删除

2.2 串的插入

2.3 串的修改

3. 具体实现

热门文章

最新文章

相关电子书