串

定义

串，即字符串（String）是由零个或者多个字符组成的有限序列。一般记为 S = ‘a1a2…a_n’ ($n\geqslant0$)

其中，S是串名，单引号括起来的字符序列是串的值；$a_i$可以是字母、数字或者其他字符；串中字符的个数n称为串的长度。n=0 时的串称为空串（用 $\varnothing$ 表示）

字串：串中任意个连续的字符组成的子序列
主串：包含字串的串
字符在主串中的位置：字符在串中的序号
字串在主串中的位置：字串的第一个字符在主串中的位置
位序是从1开始，而不是0开始

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

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查通常以字串为操作对象

串的基本操作

StrAssign(&T, chars)：赋值操作，把串T赋值为chars
StrCopy(&T, S)：复制操作。由串S复制得到串T
StrEmpty(S)：判空操作。若S为空串，则返回true，否则返回false
StrLength(S)：求串长，返回串S的元素个数
ClearString(&S)：清空操作。将S清为空串
DestroyString(&S)：销毁串。将串S销毁，回收存储空间
Concat(&T, S1, S2)：串联接。用T返回由S1和S2联接而成的新串
SubString(&sub, S, pos, len)：求字串，用sub但会串S的第pos个字符起长度为len的子串
Index(S, T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0
StrCompare(S, T)：比较操作。若S>T，则返回值>0，若S=T，则返回值=0，若S< T，则返回值<0

这个比较是一个字符一个字符比较的，那字符怎么比较呢？
ASCII字符编码，将数字与字符一一对应，因此比较字符实际上就是比较字符对应的数字

乱码问题：
不同的编码规则可能会导致乱码

存储结构

顺序存储

静态数组实现（定长顺序存储）

#define MAXLEN 255  // 预定义最大串为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;

链式存储

typedef struct StringNode{
    char ch; // 每个结点存1个字符
    struct String * next;
}StringNode, *String;

这种方式存储密度低：每个字符1B，每个结构指针4B

改进版，提高存储密度：

typedef struct StringNode{
    char ch[4];
    struct StringNode * next;
}StringNode, * String;

基本操作

求子串

基于顺序存储，静态数组实现的

bool SubString(SStriuing &Sub, SString S, int pos, int len){
    // 子串范围越界
    if (pos+len-1>S.length)
        return false;
    for (int i=pos; i<pos+len; i++)
        Sub.ch[i-pos+1] = S.ch[i];
    Sub.length = len;
    return true;
}

比较字符串

int StrCompare(SString S, SString T) {
    for (int i=1, i<=S.length && i<=T.length; i++) {
        if (S.ch[i]!=T.ch[i])
            return S.ch[i]-T.ch[i];
    }
    // 扫描过的所有字符都相同，则长度长的串更大
    return S.length - T.length;
}

定位操作

若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0

int Index(SString S, SString T){
    int i =1, n=StrLength(S), m=StrLength(T);
    SString sub; // 用于暂存子串
    while(i<n-m+1){
        SubString(sub, S, i, m);
        if(StrCompare(sub, T)!= 0)
            i++;
        else
            return i; // 返回子串在主串的位置
    }
    return 0; // S中不存在与T相等的子串
}

朴素模式匹配算法

串的模式匹配：在主串中找到模式串相同的子串，并返回其所在位置。

int Index(SString S, SString T){
    int k=1;
    int i=k,j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;
            j++;
        }else{
            k++;
            i=k;
            j=1;
        }
    }
    if(j>T.length)
        return k;
    else
        return 0;
}

朴素模式匹配算法性能
最好情况时间复杂度O(n)
最坏情况时间复杂度O(nm)
最好情况：子串之前第一个字符就不匹配
最坏情况：总是匹配到第一个字符

朴素模式匹配算法，每次回溯都只往后移动一次

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;
}

上面我们会发现一个next数组，下面就是如何算next数组的方法，next数组是用来决定不同匹配位置匹配不上的时候向右移动多少格

串的前缀：包含第一个字符，且不包含最后一个字符的子串
串的后缀：包含最后一个字符，且不包含第一个字符的子串
当第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则：
next[j] = S 的最长相等前后缀长度+1
特别地，next[1]=0

序号j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

第1个匹配不成功，直接0
第2个匹配不成功，前后缀长度都是0，加1，于是为1
第3个匹配不成功，前缀a，后缀b，相等长度为0，加1，于是为1
第4个匹配不成功，前缀ab，后缀ba，最长相等长度为1，加1，于是为2
第5个匹配不成功，前缀为aba，后缀为bab，最长相等为ab，长度为2，加1，于是为3
第6个匹配不成功，前缀为abab，后缀为baba，最长相等为aba，长度为3，加1，于是为4

求模式串T的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++;
            // 若pi=pj，则 next[j+1]=next[j] + 1
            next[i] = j;
        } else {
            // 否则令 j=next[j]，循环继续
            j = next[j];
        }
    }
}

KMP算法优化

只是优化了next数组，将next数组优化成nextval数组

主要代码为

nextval[1]=0
if (T.ch[next[j]]==T.ch[j]) {
    nextval[j] = nextval[next[j]];
} else{
    nextval[j] = next[j]
}

先手算出next数组，比如

序号j	1	2	3	4	5	6
模式串	a	b	a	b	a	a
next[j]	0	1	1	2	3	4

然后

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

判断过程
T.ch[next[2]]是a，T.ch[2]是b
因此nextval[2]=next[2]=1
T.ch[next[3]]是a，T.ch[3]是a
因此nextval[3]=nextval[next[3]]=nextval[1]=0
T.ch[next[4]]是b，T.ch[4]是b
因此nextval[4]=nextval[next[4]]=nextval[2]=1
T.ch[next[5]]是a，T.ch[5]是a
因此nextval[5]=nextval[next[5]]=nextval[3]=0
T.ch[next[6]]是b，T.ch[6]是a
因此nextval[6]=next[6]=4