【数据结构】04串

1. 定义

串(string)是由零个或多个字符组成的有限序列，又叫字符串。
一般记为s=$a_1,a_2,...,a_n,(n\ge 0)$。串中字符数目n称为串的长度。零个字符的串称为空串。

2. 串的比较

给定两个串：s=$a_1,a_2,...,a_n$，t=$b_1,b_2,...,b_m$，当满足以下条件之一时，$s<t$：
(1) $n<m$，且$a_i=b_i$，例如：$s=hap,t=happy$，就有$s<t$。
(2)存在某个$k\le \min (m,n)$，使得$a_i=b_i$，$a_k<b_k$，就有$s<t$。例如$s=happen$，$t=happy$，此时$k=4$，且字符有：$e<y$，则$s<t$。

3. 串的存储结构

串的存储结构与线性表相同，分为两种：顺序存储结构和链式存储结构。

1. 串的顺序存储结构使用一组地址连续的存储单元来存储传中的字符序列。
2. 串的链式存储结构与线性表相似，但是如果一个字符占用一个结点，就会存在很大的空间浪费。
   串的链式存储结构除了在连接串与串操作时，有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

对于串的顺序存储有一些变化，串值的存储空间可在程序执行过程中动态分配而得。

4. 具体实现

为了方便管理，利用C++的类实现了String：

#include <iostream>
using namespace std;class String
{friend ostream& operator<<(ostream& os, const String& s); // 友元函数
private:int max_size = 10;int extend_size = 10;char* ptr; // 字符指针int len;// 扩展内存void ExtendString(){char* new_ptr = new char[max_size + extend_size];memset(new_ptr, 0, sizeof(char) * (max_size + extend_size));// 拷贝数据memcpy(new_ptr, ptr, sizeof(char) * max_size);// 清空内存delete[] ptr;// 指向新内存ptr = new_ptr;// 更新最长大小max_size = max_size + extend_size;}public:String()  // 构造函数{// cout << "调用了默认构造函数" << endl;ptr = new char[max_size]; // 初始化内存memset(ptr, 0, sizeof(char) * max_size);len = 0; // 字符串长度}String(const char* s) // 构造函数{cout << "调用了构造函数" << endl;int len = strlen(s);ptr = new char[this->max_size]; // 初始化内存memset(ptr, 0, sizeof(char) * this->max_size);while (this->max_size < len){ExtendString();}// 拷贝数据memcpy(this->ptr, s, sizeof(char) * len);this->len = len;}String(const String& s) // 构造函数{cout << "调用了拷贝构造函数" << endl;ptr = new char[s.max_size]; // 初始化内存memset(ptr, 0, sizeof(char) * s.max_size);// 拷贝数据memcpy(ptr, s.ptr, sizeof(char) * s.len); // 拷贝字符串len = s.len;max_size = s.max_size;}String& operator=(const char* str) // 赋值函数{cout << "调用了重载的赋值函数char*" << endl;int len = strlen(str);while (strlen(str) > this->max_size){ExtendString();}memcpy(this->ptr, str, sizeof(char) * len);this->len = len;return *this;}String& operator=(const String& str) // 赋值函数{cout << "调用了重载的赋值函数String" << endl;while (str.max_size> this->max_size){ExtendString();}memcpy(this->ptr, str.ptr, sizeof(char) * str.len);this->len = str.len;return *this;}// 清空字符串void clear() {memset(ptr, 0, sizeof(char)*max_size); // 内存置0len = 0;}// 返回字符串长度int length()const {return len; }// 返回从第pos个字符开始，长度为len的子串String sub(int pos, int len) {// 创建临时对象String tmp;for (int i = 0; i < len; i++){tmp.ptr[i] = this->ptr[i + pos - 1];}tmp.len = len;return tmp;}// 将str插入到当前字符第pos个字符之后String Insert(int pos, const String& str){int whole_len = str.len + this->len;while (this->max_size < whole_len){ExtendString();}// 插入字符// 1.保存第pos个字符之后的所有字符，后移str_len位 即：pos-1开始的len-pos个字符移动到pos+str_len-1for (int i = this->len; i > pos; i--){this->ptr[i + str.len - 1] = this->ptr[i - 1]; // }// 2.插入字符从 str.ptr[0]到 str.ptr[len-1] 到pos-1至pos+str.len-1;memcpy(&(this->ptr[pos]), &(str.ptr[0]), sizeof(char) * str.len);this->len = whole_len;return *this;}~String(){delete[] ptr;ptr = nullptr;len = 0;}bool operator<(const String& str)const{int i = 0;for (i = 0; i < this->len && i < str.len; i++){if (this->ptr[i] == str.ptr[i]){continue;}if (this->ptr[i] > str.ptr[i]) // 前面都相等，一旦有一个字符大，则整个字符串都大{return false;}else // 前面都相等，当前字符小{return true;}}if (this->len < str.len)// 退出比较的原因是前面字符都相等，但当前字符串的字符较短{return true;}return false;}bool operator>(const String& str)const{int i = 0;for (i = 0; i < this->len && i < str.len; i++){if (this->ptr[i] == str.ptr[i]){continue;}if (this->ptr[i] < str.ptr[i]) // 前面都相等，一旦有一个字符小，则整个字符串都小{return false;}else // 前面都相等，当前字符大{return true;}}if (this->len > str.len)// 退出比较的原因是前面字符都相等，但当前字符串的字符更长{return true;}return false;}
};// 重载输出
ostream& operator<<(ostream& os, const String& s)
{for (int i = 0; i < s.len; i++){os << s.ptr[i];};return os;
}int main(void)
{String s1;s1 = "ace";String s2 = s1;String s3("bdf");String s4 = "asw";  // 自动类型转换，调用赋值函数/*s3 = s2.sub(1, 2);*/cout << s1 << endl;s1.clear();cout << s1 << endl;cout << s2 << endl;cout << s3 << endl;cout <<( s3 < s2) << endl;s2.Insert(3, s3);cout << s2 << endl;return 0;
}

5. 模式匹配

在一段字符串中去定位子串的位置的操作称作串的模式匹配，这是串中最重要的操作之一。
假设我们要从主串"S=goodgoogle"中，找到子串"T=google"的位置。通常需要进行下面的步骤：

1. 主串S第一位开始，S与T的前三个字符都匹配成功，但S的第四个字符为"d"而T的第四个字符为"g"。第一位匹配失败。
2. 主串S第二位开始，S首字符为"o"而T的首字符为"g"，第二位匹配失败。
3. 同理，第三位和第四位都匹配失败
4. 主串第五位开始，S与T，6个字母全匹配，匹配成功。

简单来说，对主串的每个字符作为子串开头，与要匹配的子串进行匹配。对主串做外部循环，每个字符开头做子串T长度的内部循环，直到匹配成功或主串遍历完成为止。

5.1 常规思路实现

		int Index(const String& T){int i, j = 0;for (i = 0; i < this->len; i++){for (j = 0; j < T.len; j++){if (this->ptr[i+j] == T.ptr[j]) // 主串以i开头的T长度的子串匹配{continue;}break;}if (j == T.len) // 子串匹配成功{return i; // 返回此时子串在主串中的位置}}return -1; // 匹配失败}

5.2 KMP模式匹配算法

常规思路的匹配算法需要挨个遍历主串和子串，效率低效。KMP算法的思路是当发现某一个字符不匹配的时候，由于已经知道之前遍历过的字符，利用这些信息避免暴力算法中"回退"的步骤。
KMP算法的原理：
1）在匹配过程中，主串的指针不需要回溯，只回溯子串的指针。
2）如果子串和主串中前n个字符匹配成功，遇到匹配失败的字符时，子串回溯的下标由子串的内容决定（回溯到：匹配失败前，子串内容最长相等前后缀 的长度），然后继续比较。
前缀：包含首位字符但不包含末位字符的子串。如：ababa的前缀包括：a，ab，aba，abab
后缀：包含末位字符但不包含首位字符的子串。如：ababa的后缀包括：a，ba，aba，baba。
则对于字符串:ababa最长公共前后缀为：aba。
具体流程：依次匹配主串和子串的字符，当遇到子串与主串字符不匹配时，子串指针回溯，并从回溯的位置继续与主串当前位置字符比较。如图中所示：ABABABCAA与ABABC匹配，当遇到主串字符A时，子串字符为C，此时无法匹配，子串指针回溯到第3个字符即A处，继续比较。KMP算法的关键是如何获取子串回溯位置，即next数组。

5.2.1 next数组计算

对于子串：ABABC
第一个字符A，没有前缀没有后缀，对应的next数组值为0。
第二个字符AB，包含的前后缀有：A B 对应的next数组值为1。
第三个字符的子串为ABA，包含的前后缀有：A A AB BA ，最长的长度为1。则next数组值为1。
第四个字符的子串为ABAB，包含的前后缀有：A B AB AB ABA BAB，最长的公共前后缀长度为2。next数组值为2。
第五个字符的子串为ABABC，包含的前后缀有：A C AB BC ABA ABC ABABA BABC，最长的公共前后缀长度为0。next数组值为0。
因此对于ABABC的next数组值为：0，1，1，2，0。

对于子串：AABAAF计算next数组：
初始化：i 和 j 其中i指向的是后缀末尾，j指向的是前缀末尾即把S[0,j]看作是子串，把S[1,i]看作是主串来理解。初始时j=0，i=1；next[0]=0。
前后缀不同的情况：S[i]!=S[j]，此时需要查询next[j-1]的值，查询到j需要回退的位置，必须要满足j>0，直到
S[i]==S[j]或者回退到初始位置。
前后缀相同的情况：S[i]==S[j]，j++。
更新next数组：next[i]=j。
模拟运行：

• 初始化：next[0] = 0. i =1 ,j =0.
• i=1,j=0.S[0]=A==S[1]=A => j++，j=1. next[1]=1.
• i=2,j=1;S[1]=A != S[2]= B => j=next[j-1]=next[0]=0 ，S[0]!=S[2] j>0. next[2] = 0.
• i=3,j=0;S[0] =A ==S[3]=A => j++，j=1. next[3] = 1.
• i=4,j=1;S[1]=A == S[4]= A => j++，j=2. next[4] = 2.
• i=5,j=2;S[2]=B!=S[5]=F =>j = next[j-1]=next[1] = 1 ，S[1]!=S[5] j=next[j-1]=next[0]=0 j>0.next[5]=0.
  

5.2.1 代码计算next数组

	// 获取next数组int* getNext(){// 创建next数组，长度与字符串长度一致delete[] next;next = new int[this->len];memset(next, 0, sizeof(int) * this->len);// 初始化int i, j = 0;next[0] = 0;for (i = 1; i < this->len; i++){// 前后缀不相同的情况while (j > 0 && ptr[i] != ptr[j]){// 回溯jj = next[j - 1];}// 前后缀相同的情况if (ptr[i] == ptr[j]){j++;}// 更新nextnext[i] = j;}return next;}

5.2.2 KMP算法实现

/ KMP算法int KMP(String& T){// 获取子串next数组int* next_ptr = T.getNext();// 开始匹配int i = 0, j = 0;while (i < len){if (ptr[i] == T.ptr[j]) // 匹配成功{i++; j++;}else if (j > 0) // 匹配失败，子串指针回溯，并且需要保证回溯位置不越界（即无法回溯到首个字符前）{j = next_ptr[j - 1];}else // 子串第一个字符就匹配失败i++;if (j == T.len)// 子串已经到达末尾，即全部匹配上{return i - j; // 返回位置}}return -1; // 匹配失败}