4.1 串的定义

字符串简称串，是一种由零个或多个字符多个字符组成的有限序列

串.png

• 字串：串中任意个来纳许的字符组成的子序列
• 主串：包含子串的串
• 字串在字符中的位置：字符在串中的序号
• 字串在主串中的位置：字串第一个字符在主串中的位置

1、字串的任意个，即n可以为0
2、字符串的位序从1开始而不是从0开始
3、空格也算一个字符

4.2 串的基本操作

StrAssign(&T, chars) 赋值，把串T赋值为chars
StrCopy(&T,S) 复制，由串S复制得串T
StrEmpty(S) 判空
StrLength(S) 求串长，即S的元素个数
ClearString(&S) 清空，将S清为空串
DestotyString(&S) 销毁串，将S销毁，回收存储空间
Concat(&T, s1, s2) 串连接，用T返回s1和s2连接的字符串
SubString(&Sub, S, pos, len)求字串，用Sub返回串S第pos个字符起长度为len的字串
Index(S,T)定位，若S中存在T相同字串，返回第一次出现的位置，否则返回0
StrCompare(S,T)， 比较，若S>T返回>0，若S<T，返回<0

4.3 串的存储结构

4.3.1 顺序存储

4.3.1.1 初始化

typedef struct {
    char ch[MaxSize];
    int length;// 串实际长度
}SString;

4.3.1.2 求字串

bool SubString(SString S, SString * sub, int pos, int len)
{
    // 首先判断子串是否包含在当前字符串内
    if (pos + len  -1 > S.length) return false;
    for (int i = pos; i < pos+len; i++)
    {
        sub.ch[sub.pos+1] = S.ch[i];
    }
    sub.length = len;
    return true;
}

4.3.1.3 比较

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

4.3.1.4 定位

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

4.3.2 堆分配存储结构

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

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

4.3.3 块链存储

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

4.4 串的模式匹配

子串是主串的一部分，一定存在，模式串不一定能在主串中找到

4.4.1 朴素模式匹配算法

int Index(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 + 1;
    else return 0;
}

最多对比n-m+1次
时间复杂度为O(nm)

4.4.2 KMP算法

void Index_KMP(SString S, SString T, int pos){
    // i 目标串指针，j 模式串指针
    i = pos; j = 1;
    while( i <= length(S) && j <= length(T)){
        // 如果将要和 目标串元素 匹配的元素是模式串首元素前一位的元素
        // 当前目标串元素 和 模式串元素可以匹配
        // if (j == first_indexof(T) - 1 || S[i] == T[j]){
        if(j == 0 || S[i] == T[j]){
            // 指针各自右移一位，这也是为什么j==0时需要放在一起判断的原因
            ++i;
            ++j;
        }else{
            // 发生了失配，查Next数组移动模式串指针
            j = next[j];
        }
    }
    if (j > length(T)){
        // 如果模式串指针溢出了（模式串指针匹配完毕了所有模式串中的元素）
        return i - length(T);
    }
    else return 0;
}

KMP算法主要掌握手算next数组的方法，其中next[1]=0,next[2]=1