第四章-串

4.1 串的定义和实现

1.什么是串

字符串，简称串，在 c++语言中使用关键字 string 来定义

string a = "this is a string";

2.串的存储结构

• 1.定长顺序存储表示（本质上就是字符数组）

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN + 1]; // 一般下标从1开始，0不用，这样可以简便一些算法
    int length;
} SString;

串的实际长度只能小于等于 MAXLEN，超过预定义长度的串值会被舍去，称为截断

• 2.堆分配存储表示

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

• 3.块链存储表示

#define CHUNKSIZE 80       // 块的大小可由用户自定义
typedef struct Chunk{
    char ch[CHUNKSIZE];    // 称为块
    struct Chunk* next;
} Chunk;

typedef struct{
    Chunk *head, *tail;    // 串的头指针和尾指针
    int curlen             // 串的当前长度
}LString;                   // 字符串的块链结构

3.串的基本操作

• 串的基本操作，可以看下面两个链接
• 主要包括构造、销毁、清空、求串长、求字串等 "c 语言的库cstring"

"c++的库string"

• 串的基本操作
  • StrAssign(&T, chars)：串赋值
  • StrCompare(S, T)：串比较
  • StrLength(S)：求串长
  • Concat(&T, S1, S2)：串连结
  • SubString(&Sub, S, pos, len)：求子串
  • StrCopy(&T, S)：串拷贝
  • StrEmpty(S)：串判空
  • ClearString(&S)：清空串
  • Index(S,T,pos)：子串的位置
  • Repalce(&S, T, V)：串替换
  • StrInsert(&S, pos, T)：子串插入
  • StrDelete(&S, pos, len)：子串删除
  • DestoryString(&S)：串销毁

4.2 串的匹配模式

1.简单的模式匹配算法--BF 算法

int Index_BF(SString S, SString T, int pos) {
int i = pos, j = 1;
while (i <= S.length && j <= T.length) {
if (S.ch[i] == T.ch[j]) {// 比较成功则继续匹配下一个字符串
    i++;       //主串比较位置 S-->i
    j++;        //字串比较位置 T-->j
    }
else { // 比较不成功则回溯
    i = i - j + 2;
    j = 1;
    }
}
if (j > T.length)  
    return  i - T.length;  // 看下文注释
else 
    return 0;
}

/*
j >= T.length 是错误的，举个反例：
S = {"abcdef"}; T = {"fg"}
when i = 6;
S.ch[i] = T.ch[j] = 'f';
Then i=7; j=2;
此时不符合循环条件跳出。明显j = 2匹配成功了
*/

时间复杂度$O(mn)$

2.改进的模式匹配算法--KMP 算法

• 1.概念

  • 前缀：除最后一个字符外，字符串所有的头部字串
  • 后缀：除第一个字符外，字符串所有的尾部字串
  • 部分匹配值：字符串的前后缀的最长相等前后缀长度

• 2.主函数

int Index_KMP(SString S, SString T, int pos) {
int i = pos, j = 1;
while (i <= S.length && j <= T.length) {
if (j == 0 || S.ch[i] == T.ch[j]) { // j == 0或者比较成功则继续匹配下一个字符串
    i++;
    j++;
}
else
    j = next[j] // 比较不成功则回溯
}
if (j > T.length)  return  i - T.length;  // 看下文注释
else return 0;
}

• 3.获得next函数

void Get_next(SString T, int nextval[]){
int i = 1, j = 0;
nextval[1] = 0;
while (i < strlen(T)) {
if (j == 0 || T.ch[i] == T.ch[j]) next[++i] = ++j;
    else next[i] = next[j];
else j = next[j]; // 隐含着非常厉害的递归思想
}
return 0;
}

时间复杂度$O(m+n)$ ，其中$O(m)$ 来自于求next数组，$O(n)$ 来自KMP算法的里层循环（普通模式匹配算法的时间复杂度是$O(mn)$

3.EXP 'ababa'

• 部分匹配值
  • 'a'--> 0
  • 'ab'--> 0
  • 'aba'--> 1
  • 'abab'--> 2
  • 'ababa'--> 3
• next数组
  • 右移一位，首位-1，末位溢出
    • -1 0 0 1 2
• 简洁next数组
  • 各位+1
    • 0 1 1 2 3

4.KMP 算法的进一步优化

• 再次递归，将 next[j] 修正为 next[next[j]]
• 获得 nextval 函数

void Get_next(SString T, int nextval[]){
int i = 1, j = 0;
nextval[1] = 0;
while (i < strlen(T)) {
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]; // 隐含着非常厉害的递归思想
}
return 0;
}