数据结构第五章 串

串：串是由零个或多个字符串组成的有限序列，又名叫字符串 。一般记为
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'

//获取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]的结果为：

当子串和模式串不匹配时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];
    }
}