串

• 内容受限的线性表
• 内容只能是字符

定义

串（string）是由零个或多个任意字符组成的有序序列 又名字符串

(用双引号括起来有些书中也用单引号)所谓序列说明串的相邻字符之间具有前驱和后继关系

空格串：由一个或多个空格组成的串，与空串不同，空格串有内容有长度且只由空格组成

子串：串中任意个连续的字符组成的子序列(含空串)称为该串的子串

主串：包含子串的串就相应的称为主串

字符位置：字符在序列中的序号为该字符在串中的位置

子串位置：子串第一个字符在主串中的位置

串相等：当且仅当两个串长度相等，并且各个对应位置上的字符都相同时，这两个串才是相等的

所有的空串都相等

串的应用非常广泛，计算机的大多数非数值处理的对象大多数是字符串数据，例如：文字编辑、符号处理，各种信息系统等等

串的基本操作

假设有串 T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'

• 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的子串；

• SubString(&Sub, S, pos, len): 求子串，用Sub返回串S的第pos个字符起长度为len的子串；

串的存储结构

定长顺序存储表示

#define MaxLen 255 //预设最大串长为255typedef struct {char ch[MaxLen];  //静态数组实现（定长顺序存储）//每个分量存储一个字符//每个char字符占1Bint length;     //串的实际长度
}SString;

• 串长的两种表示法：

• 方案一：用一个额外的变量length来存放串的长度（保留ch[0]）；

• 方案二：用ch[0]充当length；
  优点：字符的位序和数组下标相同；

• 方案三：没有length变量，以字符’\0’表示结尾（对应ASCII码的0）；
  缺点：需要从头到尾遍历；

• **方案四——最终使用方案：**ch[0]废弃不用，声明int型变量length来存放串的长度（方案一与方案二的结合）

• 基本操作实现（基于方案四）

• #include
  #include#define MaxLen 255 //预设最大串长为255typedef struct {char ch[MaxLen];  //静态数组实现（定长顺序存储）//每个分量存储一个字符//每个char字符占1Bint length;     //串的实际长度
  }SString;//求子串
  bool subString(SString* 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;
  }//比较两个串的大小
  int StrCompare(SString S, SString T)
  {for (int i; 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;
  }//定位操作
  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;elsereturn i;    // 返回子串在主串中的位置}return 0;            //S中不存在与T相等的子串
  }

2.堆分配存储表示

**堆存储结构的特点：**仍以一组空间足够大的、地址连续的存储单元依次存放字符序列，但它们的存储空间实在程序执行过程种动态分配的 。
通常，C语言提供的串类型就是以这种存储方式实现的。由动态分配函数malloc()分配一块实际串长所需要的存储空间（“堆”），如果分配成功，则返回此空间的起始地址，作为串的基址。由free()释放串不再需要的空间，

**堆存储结构的优点：**堆存储结构既有顺序存储结构的特点，处理（随机取子串）方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常被采用。

//动态数组实现
typedef struct{char *ch;           //按串长分配存储区，ch指向串的基地址int length;         //串的长度
}HString;HString S；
S.ch = (char *) malloc(MAXLINE * sizeof(char)); //基地址指针指向连续空间的起始位置//malloc()需要手动free()
S.length;

3.串的链式存储

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

问题：存储密度低，每个字符1B，每个指针4B；

解决方案：每一个链表的结点存储多个字符——每个结点称为块——块链结构

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

结合链表思考优缺点

• 存储分配角度：链式存储的字符串无需占用连续空间，存储空间分配更灵活；
• 操作角度：若要在字符串中插入或删除某些字符，则顺序存储方式需要移动大量字符，而链式存储不用；
• 若要按位序查找字符，则顺序存储支持随机访问，而链式存储只支持顺序访问；

串的匹配算法

算法目的：确定主串中所含子串（模式串）第一次出现的位置（定位）

有用的算法如文章中查找关键字、搜索引擎、拼写检查、语言翻译、数据压缩

BT算

int index_BF(SString S, SString T, int pos)
{//返回模式T在主串中第pos个字符开始第一次出现的位置，若不存在返回值为0；//其中，T非空，1≤pos≤S.lengthint i = pos;     int 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;   //匹配不成功}
}

KMP算法

BF算法效率低下的原因

1. 让主串和模式串挨个字符进行比较

2. 如果遇到了不相等的字符则让模式串后移一位，并且让指针重新指向模式串的第一个字符，然后继续进行比较

KMP算法设计思想

• 利用已经部分匹配的结构而加快模式串的滑动速度。
• 主串S的指针 i 不必回溯！ 可提速到O(n+m)

KMP 算法的做法就是仅仅后移模式串就能让两个串的每一个字符进行比较，从而找出子串

例一

1. 回到一开始发现第一个出现字符不匹配的位置，可以发现 ，不匹配的字符（箭头）左边的字符主串和模式串是完全匹配的

2. 模式串左右两端都有一个相等AB两个子串，这两个相等的子串称为模式串的公共前后缀。

3. 核心：接下来直接移动模式串，将公共前后缀例的前缀直接移动到原来的后缀的位置

4. 这样移动了之后就会让比较指针左边的主串和模式串中的内容一致，因为公共前后缀的值是相匹配的，移动之前左边主串和模式串的内容是匹配的，移动之后当然也是匹配的
5. [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DHNn6pTK-1678849235623)(F:\BaiduSyncdisk\计算机\数据结构 王卓\17ec434037b949ddaf51cd5bc03b82a1.png)]

​ 只要记录下出现不匹配的字符的位置，然后在字符指针前面的字符内容中找出模式串的公共前后缀，最后再直接将前缀移动到后缀，这样就可以继续往下比较了，省时省力

• 注意：如果模式串中出现了多对公共前后缀，要取最长的那对
• 后缀的位置一定是不匹配的位置相邻的。

5. 当走到下一个不匹配的位置时，继续重复以上步骤，寻找最长公共前后缀，然后将前缀移动到后缀的位置

   • 与后缀对称相等的字符(或字符串)就称为前缀

   

• 这时候发现，模式串已经超出了主串的范围，已经可以判定匹配失败，主串中不含有模式串相同的子串

例二

• 最长公共前后缀应该要小于标记指针左边的子串，如果前后缀取下图这样的那就没有意义了

• 所以模式串的最长公共前后缀应该是这样的。

• 

• 让前缀移动到后缀的位置。

• 移动完了之后继续比较，找到不相等的字符的话，就继续找 最长公共前后缀，然后移动。

• 移动好了之后再继续比较模式串，比较指针一直移动到最后都没有找到不匹配的字符，这时候就可以判断主串中有包含模式串的子串。

挖掘模式串

• 使用 KMP 算法的过程中可以发现，在移动模式串的时候压根不需要用到主串，把主串扔掉照样能将前缀移动到后缀。

• 这样将模式串的内容挖出来之后就可以和任何的主串进行比较了，前面说过，模式串从数组下标为1的位置开始存储比较方便观看。

1. 假设模式串和子串第一位就出现了不匹配，因为标记指针左边的子串的内容直接等于公共前后缀，前面说过，指针左侧的长度不能等于公共前后缀的长度，所以此处模式串指针只能移动1位。

2. 让模式串中1号位的字符与主串中二号位的字符进行比较，如果还不相等，则让模式串中的第1位字符和主串的第三位字符比较。公共前后缀长度为0的时候，模式串只能移动1位。

3. 在比较指针移动到主串的4号位的时候发现，公共前后缀长度终于不为0了，操作还是一样，前缀——>后缀。

• 然后让模式串的 2 号位与主串当前位置（4号位）的字符进行比较

4. 找主串的 5 号位对应的模式串左边的最长公共前后缀，然后移动模式串，让模式串当前的 3 号位与主串当前位置（5号位）的字符进行比较。

5. 然后看对应主串 6 号位的情况，操作依然不变，找公共前后缀，移动位置，模式串 4 号位与主串当前位（6号位）比较。

总结

• 如果公共前后缀长度为 n 。
• 我们就得到将模式串的 n + 1号位与主串当前位开始比较。
• 每次开始比较的编号就是最大公共前后缀长度+1

• 比如：此时比较指针到了模式串的 7 号位置，左边的最大公共前后缀长度是1，移动之后就是将模式串的2号位置的字符与主串的当前位置进行比较。

噼里啪啦一顿操作之后

• 我们将第一句话的内容给他标记为 0，当看到这个 0 的时候就按照第一句话描述的内容（1号位与主串下一位比较）来处理，if(0){则按照第一句话的内容来做}

• 将后面每句话对应的数字都拿出来，作为每句话的内容所要执行的代号。

• 

• 然后再结合上面的数组下标，将他们放到一个数组中，这样一来根据数据中所提供的信息，任何一个位置发生了不匹配，自动就知道下一步该怎么做了。

  • 比如：模式串的0号位置（对应数组的1号位）不匹配，自然知道该干啥。这样一个数组就称为 next 数组。