数据结构第五章 串

文章目录[x]
  1. 1:串长、空串、空格串、子串、主串
  2. 1.1:串是一种特殊的线性表,数据元素之间呈线性关系
  3. 1.2:串的基本操作
  4. 1.3:串的模式匹配

串:串是由零个或多个字符串组成的有限序列,又名叫字符串 。一般记为
S = 'a_1a_2...a_n' (n>=0)
其中,S是串名,单括号内的字符序列是串的值。

串长、空串、空格串、子串、主串

串长:串中字符的个数n。例:'abc' , n=3

空串:n=0时的串称为空串。

空格串:由一个或多个空格组成的串。例: ' ' (4个空格),n=4

子串:串中任意个连续的字符组成的子序列。例如:A='hello world',B='hello',C='word',B和C都是A的子串

主串:包含子串的串。上面例子中A就是主串

串的位置:某个字符在串中的序号称为该字符在串中的位置。上例中B在A中的位置是1,C在A中的位置是7.

串是一种特殊的线性表,数据元素之间呈线性关系

串的数据对象限定为字符集

串的基本操作大多以“子串”作为操作对象

串的基本操作

  • StrCopy (&T,S),复制操作,由串S复制得到串T。

  • Index (S,T),定位操作,找到串T在主串S中的位置。

  • StrLength (S),求串长,返回串S的元素个数。

  • StrCompare (S,T);比较操作。若S>T,则返回值>0,若S=T,则返回值=0,若S<T,则返回值<0。

    ​ 【注】每个字符在计算机中对应一个二进制数,比较字符的大小就是比较二进制数的大小

串的模式匹配

子串的定位操作通常称为串的模式匹配,它求的是子串(常称为模式串)在主串中的位置。

简单的模式匹配算法(朴素模式匹配)

将主串S中与需要定位的子串相同长度的字符拎出来,挨个与子串匹配。若子串与模式串某个字符不匹配时,立即放弃该子串,转而检索下一子串。

例:主串:'abacababc' 模式串:'abc'

主串中与模式串长度相同的子串有'aba','bac','aca','cab','aba','bab','abc'。(也可以直接比较,不拎出来,看个人理解)依次与模式串比较,最后得到模式串在主串中的位置是7。

//暴力模式匹配
int Index(SString S,SString T){   //主串S,模式串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;
}

若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较
最坏时间复杂度: 0(nm)
最坏情况:每个子串的前m-1个字符都和模式串匹配,只有第m个字符不匹配,比较好的情况:每个子串的第1个字符就与模式串不匹配

朴素模式匹配算法的缺点:当某些子串与模式串能部分匹配时,主串的扫描指针i经常回溯,导致时间开销增加。最坏时间复杂度0(nm)

KMP算法

当子串和模式串不匹配时,主串指针i不回溯,模式串指针j=next[j]。next[j]的含义是:在子串的第j个字符与主串失配时,则跳到子串的next[j]位置重新与主串当前位置进行比较。

next数组手算方法:当第j个字符匹配失败,由前1~j-1个字符组成的串记为S,则:
next[j]=S的最长相等前后缀长度+1,特别地,next[1]=0;值得注意的是,有些地方next[1]=-1,这也是没问题的,只要计算出的数组所有数都减一就可,其实就是最长相等的前后缀长度。

例:主串:'abacababacaabacb' 模式串:'abacb'

编号 1 2 3 4 5
模式串 a b a c b
next[j] 0 1 1 2 1
//获取next数组
void get_next(SString T,int next[]){
    int i=1,j=0;
    next[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i;++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
//KMP算法
int Index_KMP(SString S,SString T,int next[]){
    int i=1,j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            ++i; 
            ++j;  //继续比较后继字符
        }
        else
            j=next[j]; //模式串向右移动
    }
    if(j>T.length)
        return i-T.length;  //匹配成功
    else 
        return 0;
}

算法平均时间复杂度: 0(n+m)

KMP算法进一步优化

nextval数组的求法:先算出next数组,先令nextval[1]=0,比较模式串中字符与其对应next[j]位置的字符是否相同,若相同,则将next[j]的值设为一致,否则不做改变。

上个例子中的nextval[j]的结果为:

编号 1 2 3 4 5
模式串 a b a c b
next[j] 0 1 1 2 1
nextval[j] 0 1 0 2 1

当子串和模式串不匹配时j=nextvalj];

//获取nextval数组
void get_nextval(SString T,int nextval[]){
    int i=1,j=0;
    nextval[1]=0;
    while(i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            ++i;++j;
            if(T.ch[i]!=T.ch[j])  nextval[i]=j;
            else nextval[i]=nextval[j];
        }
        else
            j=nextval[j];
    }
}

在这里插入图片描述

点赞
  1. Fmaesp说道:

    paper writing online - write me a essay buying an essay

  2. Psdxhc说道:

    canadian pharmacy review - http://canadaxpha.com/ best online pharmacy canadaxpha.com

  3. Xagicb说道:

    cheap tadalafil - http://cialirpl.com/ tadalafil generic Generic cialis online

  4. Xkxzlv说道:

    treatments for ed - https://goedpls.com/ ed pills gnc ed pills

  5. Sewyol说道:

    top erection pills - https://oxcial.com/ generic cialis tadalafil 20 mg from india Cialis online

  6. Iwrixa说道:

    cialis generic date http://cadciali.com/ cialis buy cialis cialis internet Srxikg xanfol

  7. Vmpmvt说道:

    canadian pharmacy review - http://canadianpharmpl.com/ canadian pharmacy online canadian pharmacy cialis

  8. Azmkxf说道:

    online viagra - https://sildefinik.com/ viagra without doctor sildefinik.com

  9. Zolhcl说道:

    doubleu casino https://slotgmsp.com/ casino slot games real online casino Irqcqe upeqwe

  10. Rfvbdv说道:

    real casino online https://casaslotsg.com/ gambling games rivers casino Bnkfqc ebmatn

  11. Hoylii说道:

    discount cialis https://okviacia.com/ casinos viagra dosage Zvhnlg juppjh

  12. Yqxdby说道:

    cialis buy https://tadalapi.com/ casino online buy cialis Szxrdq brmbgz

  13. Szjmvz说道:

    best place to buy cialis online reviews https://cilipili.com/ best casino online buy generic cialis Xlmdyi hhuxlt

  14. Olqdqj说道:

    canadian pharmacy cialis 5mg https://pharstores.com/ canadian pharmacy viagra canadian discount pharmacy Jqmemn dbwaid

  15. Quphxk说道:

    the best ed pill https://edpionline.com/ best erectile dysfunction pills overcoming ed Fmrpxr mwukzv

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00