基本概念

串(String)——零个或多个任意字符组成的有限序列

image-20220907162402285

空串:n=0,用 $\phi$ 表示

子串:一个串中任意个连续字符组成的子序列(含空串)称为该串的子串。

例如,“abcde”的子串有:

“ ”、“a”、 "ab”. "abc”. " abcd” 和 “abcde” 等

真子串:是指不包含自身的所有子串。

主串:包含子串的串相应地称为主串

字符位置:字符在序列中的序号为该字符在串中的位置

子串位置:子串第一个字符在主串中的位置

空格串:由一个或多个空格组成的串,与空串不同

例如 字符串:a、b、c、d
长度子串
a = ‘BEI’3\
b = ‘JING’4\
c = ‘BEIJING’7a
d = ’BEI JING’8b

ac 中的位置是:1 ; ad 中的位置:1;bc 中的位置是:4 ; bd 中的位置:5;

串相等:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才足相等的。所有空串是相等的。

串的类型定义

image-20220907173435689

串的存储结构

串中元素逻辑关系与线性表的相同,串可以采用与线性表相同的存储结构。

image-20220907173759635

  • 串的顺序存储结构:
#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];    // 存储串的一维数组 数组长度为0~255即256,但是下标为0的位置基本上不用;
    int length;    // 串的当前长度
}SString
  • 串的链式存储结构

image-20220907174547687

优点:操作方便;缺点:存储密度较低

$存储密度=\frac{串值所占的存储}{实际分配的存储}$

解决办法:

可将多个字符存放在一个结点中,以克服其缺点,即块链结构:

image-20220907175016298

  • 块链结构
#define CHUNKSIZE 80 //块的大小可由用户定义
typedef struct Chunk{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;

typedef struct{
    Chunk *head,*tail; //串的头指针和尾指针
    int curlen; //串的当前长度
}}LString;//字符串的块链结构

串的模式匹配算法

算法目的:

确定主串中所含子串(模式串电)第一次出现的位置(定位)

算法应用:

  • 搜索引擎、拼写检查、语言翻译、数据压缩

算法种类:

  • BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的)
  • KMP算法(特点:速度快)

BF算法

Brute-Force简称为BF算法,亦称简单匹配算法。采用穷举法的思路。

image-20220907180724613

算法的思路是从 S 的每一个字符开始依次 T 的字符进行匹配。

  • 匹配失败:i = i-j+2(回溯);j=1(从头开始)
  • 匹配成功:i=7,j=5(检测完都相同时i,j均后移一位,发现没有元素了,跳出循环),返回 i-t.length = 3

DS

【算法步骤】

  • 将主串的第 pos 个字符和模式串的第一个字符比较

    • 若相等,继续逐个比较后续字符;
    • 若不等,从主串的下一字符起,重新与模式串的第一个字符比较。

      • 直到主串的一个连续子串字符序列与模式串相等。返回值
        S 中与T匹配的子序列第一个字符的序即匹配成功。
      • 否则,匹配失败,返回值 О

【算法实现】

int Index_BF(SString S,SString T){
    int i=1,j=1;
    while(i <= S.length && j <= T.length){
        if(S.ch[i] == T.ch[j]){// 主串和字串依次匹配下一个字符
            ++i;++j;
        }else{ // 主串、字串指针回溯重新开始下一次匹配
            i = i-j+2;
            j = 1;
        }
        if(j > T.length) return i-T.length;// 返回匹配的第一个字符的下标
        else return 0;//模式匹配不成功
    }
}

算法的时间复杂度分析:

若 $n$ 为主串长度,$m$ 为子串长度,最坏情况是

  • 主串前面 $n-m$ 个位置都部分匹配到子串的最后一位,即这 $n-m$ 位各比较了 $m$ 次
  • 最后 $m$ 位也各比较了1次

    总次数为: $(n-m)*m+m =(n-m+1)*m$

    若 $m<< n$,则算法复杂度 $O(n*m)$

KMP(Knuth Morris Pratt)算法

KMP算法是 D.E.Knuth、J.H.MorrisV.R.Pratt 共同提出的,简称 KMP算法。该算法较 BF 算法有较大改进,从而使算法效率有了某种程度的提高。

利用已经部分匹配的结果而加快模式串的滑动速度? 且主串 $S$ 的指针 $i$ 不必回溯!可提速到 $O(n+m)$!

KMP 算法只针对模式串,主串的指针始终不回溯,为此,定义 next[j] 函数,表明当模式中第 j 个字符与主串中相应字礼“失配”时,在模式中需重新和主串中该字符进行比较的字符的位置。

image-20220908140421492

举例:

sdd

练习:求下面模式串对应的 next[j]的值;

j1234567891011121314151617
模式串abcaabbcabcaabdab
next[j]01112231123456712

【算法实现】

  • next[j] 的求法
/*通过计算返回子串T的next数组。*/
void get_next(SString T,int &next[]){
    int i,j;
    i = 1; 
    j = 0;
    next[1] = 0;
  
    while(i < T.length){
  
        if(j == 0 || T.ch[i] == T.ch[j]){ /*T[i]表示后缀的单个字符,T[j]表示前缀的单个字符*/
            ++i;
            ++j;
            next[i] = j;
        }else{
            j = next[j];/*若字符不相同,则j值回溯*/
        }
    }
}
  • KMP算法主函数
// 返回子串贝在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。
// T非空,1≤ pos ≤ StrLength(S)
int Index_KMP(SString S,SString T,int pos){
    int i,j; 
    i=pos;    // i用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
    j=1;    // j用于子串T中当前位置下标值
  
    int next[255];    // 定义next数组
    get_next(T,next); // 对串T作分析,得到next数组
  
    while(i <= S.length && j <= T.length){
        if(j == 0 || S.ch[i] == T.ch[j]){// 主串和字串依次匹配下一个字符
            ++i;++j;
        }else{ // i不变,j后退
            j = next[j];
        }
        if(j > T.length) return i-T.length;// 返回匹配的第一个字符的下标
        else return 0;//模式匹配不成功
    }
}
🧐 本文作者:
😉 本文链接:https://lukeyalvin.site/archives/98.html
😊 版权说明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改:2022 年 09 月 24 日
赏杯咖啡