0x04 串

一、基本定义

串，即字符串，由零或多个字符组成的有限序列。

基本操作：

赋值操作strAssign(&T, chars)
复制操作strCopy(&T,S)
判空操作StrEmpty(S)
求串长strLength(S)
清空clearString(&S)
销毁destroyString(&S)
串拼接concat(&T,S1,S2)
求字串subString(&Sub, S, pos, len)
定位操作index(S,T)：若主串S中存在与串T值相同的字串，则返回它在主串S中第一次出现的位置，否则返回0
比较操作strCompare(S,T)：ASCⅡ码大的字符串更大，如果短串是是长串的前缀，则长串更大。

以下内容均默认字符串下标从1开始，下标0空着

二、串的存储结构

2.1 串的顺序存储

静态分配

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

动态分配

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

HString S;
S.ch = (char*)malloc(MAXLEN*sizeof(char));
S.length = 0;

2.2 串的链式存储

和一般链表的区别在于，这里需要考虑数据域和指针域所占存储空间比例问题。

若按一般链表的思路，一个结点的数据域只包含一个字符，则数据域大小仅为1B，而指针域大小可能为4B或更多，导致存储密度很低。

为了增大存储密度，应在一个结点的数据域中包含多个字符，定义如下：

typedef struct StringNode{
    char ch[4];             //一个结点存储4个字符
    struct StringNode* next;
}StringNode, *String;

三、串的基本操作实现

求子串
注意判越界
比较操作
若S>T，返回值>0；若S<T，返回值＜0；完全相同，返回0：return S.ch[i]-T.ch[i];
T为S的前缀：return S.length-T.length;
定位操作（朴素模式匹配）

$O(nm)$：

int Index(SString S, SString T){
    int i=1, n=StrLength(S), m=StrLength(T);
    SString sub;
    while(i<=n-m+1){
        SubuString(sub, S, i, m);
        if(StrCompare(sub, T)!=0) ++i;
        else return i;
    }
    return 0;
}

四、串的模式匹配

朴素模式匹配

int Index(SString S, SString T){
    int i = 1, j = 1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[i]){
            i++;
            j++;
        }
        else{
            i = （i-j+1）+1; 
            //当前匹配到了主串的i位置，已匹配了j个，(i-j+1)回到子串起始位置，再+1从下一个子串的起始位置重新开始匹配
            j = 1; 
            //从模式串的第一个字符开始重新匹配   
        }
    }
    if(j>T.length) return i-T.length;
    //全部匹配成功，此时j位于模式串最后一个字符的下一个位置
    //i也位于匹配成功的字串的最后一个字符的下一个位置
    //如主串123，模式串23，匹配成功，i=4，i-T.length=2
    else return 0;
}

时间复杂度

最好$O(n)$
最坏$O(nm)$
KMP算法

https://www.bilibili.com/video/BV1jb411V78H/?spm_id_from=333.788&vd_source=d72bbef28fe9cf2784e773c087d4d112

如何得到next数组？

对模式串进行预处理。显然next数组的大小就是模式串的长度。

以下next数组是考虑代码统一的情况，所以next[1]=0。

显然对任意模式串一定有：next[1]=0，next[2]=1。
- 手算：
- 在失配的位置前面划条分界线。记失配位置下标为k。
- 主串固定，模式串右移，直到分界线前的字符能重新对应，或模式串完全跨过分界线
- 记模式串位于分界线后的第一个位置下标为j，则next[k]=j。

完整算法实现

int kmp(SString S, SString T, int next[]){
    int i = 1, j = 1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i] == T.ch[j]){
            i++;
            j++;
        }
        else if(i==1){ //特殊情况：第一个字符就失配了
            i++;
            j=next[j];
        }
        else{
            j=next[j];
        }
    }
    if(j > T.length) return i-T.length;
    else return 0;
}

注意到由于存在“第一个字符就失配”的特殊情况，需要用else if来单独处理。为了从代码上统一，可以让next[1]=0，从而：

...
    next[1]=0;
    while(i<=S.length && j<=T.length){
        if(j == 0 || S.ch[i] == T.ch[j]){ 
            //j==0对应第一个字符就失配的特殊情况
            i++;
            j++;
        }
        else{
            j = next[j];
        }
    }
...

时间复杂度

最坏：O(m+n)，O(m)为预处理耗时，O(n)为匹配耗时

0x04 串

一、 基本定义

二、 串的存储结构