字符串（string）是由零个或多个字符组成的有限序列。 字符串的比较是通过组成字符串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号（即ASCII值）。 字符串的常见操作有： （1）将字符串指定为给定值； （2）将给定字符串复制到另一字符串； （3）清空字符串字符； （4）判断字符串是否为空； （5）返回字符串的长度； （6）比较两个字符串； （7）将两个字符串拼接成一个新的字符串； （8）提取字符串的一部分作为新的字符串； （9）在一个字符串中查找另一个给定字符串是否存在，以及该字符串开头在原字符串中的位置索引； （10）将一个字符串中部分子串替换为给定的另一字符串； （11）将给定字符串插入到另一字符串的指定位置； （12）将给定字符串的指定位置部分删除； （13）将字符串中的 字符大写转小写，及小写转大写； （14）去除字符串两边的空格。
字符串匹配问题是计算机科学中研究最为广泛的问题之一，其广泛应用于生物信息学和信息检索等领域。 常见的字符串匹配问题可以描述为：已知两个字符串，第一个字符串S长度为n，称之为母串，第二个字符串T长度为m，称之为模式串，现在要求判断模式串T是否在母串S中出现过。 解决该问题的常见算法有BF算法、KMP算法、BM算法等。BF算法的时间复杂度为O（n*m），空间复杂度为O（1）。KMP算法的时间复杂度为O（n+m），空间复杂度为O（m）。 BF算法（Brute Force）算法是朴素的模式匹配算法，其算法流程为： （1）母串S的第一个字符和模式串T的第一个字符进行比较； （2）如果相等，则继续比较下一个字符是否相等； （3）如果不相等，则选择母串S的第二个字符和模式串T第一个字母进行比较； （4）重复步骤（2）和（3），直至在母串S中匹配到模式串T或者枚举到母串末尾。
KMP算法（Knuth-Morris-Pratt字符串查找算法），通过对这个词在不匹配时本身包含的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符，提高程序运行效率。KMP算法在匹配前会预处理模式串P，得到一个fail数组。借助fail数组，可以在匹配过程中减少很多冗余的匹配操作，由此提高了算法的效率。对于字符串s=s0s1…sn-1，如果j是满足s0…j=si-j…i的最大值，则faili=j，其中sa…b表示字符串s从下标a到下标b的子串，即sasa+1…sb-1sb。对于不存在s0…j=si-j…i的情况，faili=-1。
STL中的string 其需包含头文件 其有2个类模板： （1）basic_string，通用字符串类 （2）char_traits，字符特征类 其有4个类实例： （1）string，字符串类； （2）u16string，16位字符的字符串； （3）u32string，32位字符的字符串； （4）wstring，宽字符串。 其有从字符串转换为数字的函数： （1）stoi()，转换字符串为整数； （2）stol()，转换字符串为long int； （3）stoul()，转换字符串为unsigned int； （4）stoll()，转换字符串为long long； （5）stoull()，转换字符串为unsigned long long； （6）stof()，转换字符串为float； （7）stod()，转换字符串为double； （8）stold()，转换字符串为long double。 也有从数字转换为字符串的函数： （1）to_string()，转换数值为字符串； （2）to_wstring()，转换数值为宽字符串。
basic_string可实现全部4个类实例，可用于任何字符类型 其成员函数包括： （1）size()，返回字符串的大小，即字符串中字符的个数，不包含\0； （2）length()，返回字符串的长度，即字符串中字符的个数，不包含\0，与size()完全相同； （3）max_size()，返回字符串潜在所能持有的最多元素个数，其取决于库的内部实现。但尽管如此，其也不保证一定能持有上述值所说的那么多个元素； （4）resize()，将字符串调整为给定值个数个元素，如果给定值小于现有元素个数，则删去末尾部分的元素，如果给定值较大，则调用元素的构造函数进行构造填充，来达到给定值个数； （5）capacity()，返回系统为当前字符串分配的能容纳的元素的个数，≥当前字符串的元素个数； （6）reserve()，请求系统为当前字符串分配的容量大于等于给定值； （7）clear()，清空字符串中所有元素内容，使其size=0； （8）empty()，测试字符串长度是否为0； （9）shrink_to_fit()，请求系统调整当前字符串分配的容量等于其元素个数；
（10）operator[]，返回字符串在指定索引处的元素引用，不进行索引范围有效性检查； （11）at()，返回字符串在指定索引处的元素引用，进行索引范围有效性检查，如果超出有限范围会抛出错误。所以相比于operator[]，推荐使用at()； （12）back()，返回字符串最后一个元素的引用； （13）front()，返回字符串第一个元素的引用；
（14）operator+=，在字符串的末尾拼接添加给定的另一个字符串，与append()完全相同； （15）append()，在字符串的末尾拼接添加给定的另一个字符串； （16）push_back()，在字符串末尾添加由给定的新字符； （17）assign()，为当前字符串指定给定的新的内容，并调整其元素个数； （18）insert()，在给定位置处添加由给定值构成的新字符串，其返回新插入字符串首字母所处位置的迭代器； （19）erase()，从给定位置处删除指定长度的字符串子串，其返回删除后新连接处字母处位置的迭代器； （20）replace()，使用给定的另一个字符串，从给定位置处替换指定长度的字符串子串； （21）swap()，交互2个字符串中所有字符内容； （22）pop_back()，删除字符串的最后一个字符；
（23）c_str()，返回一个指向数组的指针，该数组包含一个以null结尾的字符序列（即C字符串），该序列表示基本字符串对象的当前值； （24）data()，返回指向字符串内部用于存储其所属元素的内存数组的直接指针； （25）copy()，复制字符串指定位置后给定长度的子串到一字符数组； （26）find()，返回给定待查找字符串在字符串中第一次完全匹配时的位置，时间复杂度为O（n），与KMP算法相当； （27）rfind()，返回给定待查找字符串在字符串中最后一次完全匹配时的位置，时间复杂度为O（n）； （28）find_first_of()，返回给定待查找字符串中任意字符在字符串中第一次出现时的位置，时间复杂度为O（n）； （29）find_last_of()，返回给定待查找字符串中任意字符在字符串中最后一次出现时的位置，时间复杂度为O（n）； （30）find_first_not_of()，返回不是给定待查找字符串中任意字符在字符串中第一次出现时的位置，时间复杂度为O（n）； （31）find_last_not_of()，返回不是给定待查找字符串中任意字符在字符串中最后一次出现时的位置，时间复杂度为O（n）； （32）substr()，使用字符串的一连续部分来生成新的字符串； （33）compare()，比较两个字符串，如果相等则返回0，否则返回>0或<0。
char_traits指定字符属性，并为字符和字符序列上的某些操作提供特定的语义。其不实现上述4个类实例。 其成员函数包括： （1）eq()，比较两个字符串是否相等； （2）lt()，比较第1个字符串是否小于第二个字符串； （3）length()，返回字符串的长度，即字符串中字符的个数，不包含\0； （4）assign()，为当前字符串指定给定的新的内容，并调整其元素个数； （5）compare()，比较两个字符串，如果相等则返回0，否则返回>0或<0； （6）find()，返回给定待查找字符串在字符串中第一次完全匹配时的位置，时间复杂度为O（n），与KMP算法相当； （7）move()，将字符串从头开始的指定长度，复制到新的字符数组中，返回可重复； （8）copy()，将字符串从头开始的指定长度，复制到新的字符数组中，返回不可重复； （9）eof()，返回表示结尾处位置的值； （10）not_eof()，返回一个表示确保不是结尾处位置的值； （11）to_char_type()，返回与给定值等价的字符类型的值； （12）to_int_type()，返回与给定值等价的整数类型的值； （13）eq_int_type()，返回给的两个字符串是否等价相等。
已知有n个长度不一定相同的母串，以及一个长度为m的模式串T，求该模式串是否是其中一个母串的前缀。如果将模式串T挨个去比较，则算法复杂度很高，会达到O（n*m）。 另外一个问题，已知一个长度为n的字符串S，求该字符串有多少个不相同的子串。朴素的做法，先枚举所有子串，这样时间复杂度为O（n^2），之后再去重，这样做算法复杂度很高，即使改成Hash或者用set、map处理，整体复杂度仍然会很高。 上述两个问题可以用Trie树来高效求解。 Trie树又称为字典树或单词查找树，是一种树形结构的数据结构，常用于大量字符串的检索、去重、排序等。Trie树利用字符串的公共前缀，逐层建立起一棵多叉树。在检索时类似于在字典中查找单词，从第一个字符开始遍历，在Trie树中一层一层往下查找，这样查找效率可达O（n），n为查找字符串的长度。 Trie树有以下特点： （1）Trie树的根结点上不存储字符，其余结点上保存且只保存一个字符。 （2）从根结点出发，到某一结点上经过的字符，即是该结点对应的前缀。 （3）每个结点的孩子结点存储的字符各不相同。 （4）Trie树牺牲空间来换取时间，当数据量很大时，会占用很大的空间。如果字符串均由小写字母组成，则每个结点最多会有26个孩子结点，则最多会有26^n个用于存储的结点，n为字符串的最大长度。 Trie树常用于字符串的快速检索，字符串的快速排序与去重，文本的词频统计等。
const int ALPHABET_SIZE = 26; // trie node struct TrieNode { struct TrieNode *children[ALPHABET_SIZE]; // isEndOfWord为true时表示一个字符串结束 bool isEndOfWord; }; // 创建新的trie node (初始化为NULLs) struct TrieNode *getNode(void) { struct TrieNode *pNode = new TrieNode; pNode->isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) pNode->children[i] = NULL; return pNode; } // 箱trie树中添加表示新字符串的模式 void insert(struct TrieNode *root, string key) { struct TrieNode *pCrawl = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); pCrawl = pCrawl->children[index]; } // 标记最后的结点为叶结点 pCrawl->isEndOfWord = true; } // 利用trie树进行字符串查找 bool search(struct TrieNode *root, string key) { struct TrieNode *pCrawl = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->children[index]) return false; pCrawl = pCrawl->children[index]; } return (pCrawl != NULL && pCrawl->isEndOfWord); } int main() { string keys[] = {"the", "a", "there", "answer", "any", "by", "bye", "their" }; int n = sizeof(keys)/sizeof(keys[0]); struct TrieNode *root = getNode(); // 构造trie树 for (int i = 0; i < n; i++) insert(root, keys[i]); // 进行字符串查找 search(root, "the")? cout << "Yes\n" : cout << "No\n"; search(root, "these")? cout << "Yes\n" : cout << "No\n"; return 0; }AC自动机（Aho-Corasick automation）是一种将Trie树和KMP相结合的算法。可以利用AC自动机实现在整个字符串集中查找子串出现的总次数。 AC自动机有3个过程： （1）建立Trie树。这一步操作和Trie树一样，将若干个模式串建立起一棵Trie树。 （2）建立失败指针。这一步类似于KMP算法中建立next数组。在某个结点A上失配时，则通过失败指针指向某结点B进行下一次匹配（定义以结点A为终点的某个后缀为s1，以根结点为起点，结点B为终点的串为s2，则有s1=s2，且保证在所有这样的串中，s1和s2的长度是最大的），而不需要回溯到上一层，避免多余的匹配操作。 （3）字符串匹配。从根结点开始，沿树的路径进行匹配，如果当前结点匹配成功则继续往下一个结点匹配，否则跳转到失败指针所指的结点进行匹配。重复上述过程，直到匹配完模式串为止。 可以用广度优先搜索的方法构造失败指针。每个结点都有一个失败指针，首先将根结点的失败指针指向空，根结点的直接子结点的失败指针指向根结点。对Trie树进行广度优先搜索，每个结点的失败指针都是由其父结点的失败指针决定的。
// 先对之前的trie树代码进行改进 const int SIZE = 26; const char BASE = 'a'; class TrieNode { public: int count; TrieNode **childs; TrieNode *fail; TrieNode() { count = 0; childs = new TrieNode*[SIZE]; for (int i = 0; i < SIZE; ++i) { childs[i] = nullptr; } fail = nullptr; } ~TrieNode() { for (int i = 0; i < SIZE; ++i) { delete childs[i]; } delete[] childs; } }; // 然后在trie树的基础上建立AC自动机 class StringPatterns { private: TrieNode *root; public: StringPatterns() { root = new TrieNode(); } ~StringPatterns() { delete root; } void add_pattern(const string &pattern) { TrieNode *now = root; for (int i = 0; i < pattern.length(); ++i) { if (now->childs[pattern[i] - BASE] == nullptr) { now->childs[pattern[i] - BASE] = new TrieNode(); } now = now->childs[pattern[i] - BASE]; } now->count++; } void build_ACMachine() { root->fail = root; queue<TrieNode*> q; q.push(root); while (!q.empty()) { TrieNode *now = q.front(); q.pop(); for (int i = 0; i < SIZE; ++i) { if (now->childs[i] != nullptr) { TrieNode *child = now->childs[i]; if (now == root) { child->fail = root; } else { TrieNode *iter = now; while (iter != root && iter->fail->childs[i] == nullptr) { iter = iter->fail; } if (iter->fail->childs[i] != nullptr) { child->fail = iter->fail->childs[i]; } else { child->fail = root; } } q.push(child); } } } } int match_count(const string &buffer) { TrieNode *p = root; int total_count = 0; for (int i = 0; i < buffer.length(); ++i) { while (p != root && p->childs[buffer[i] - BASE] == nullptr) { p = p->fail; } p = p->childs[buffer[i] - BASE]; if (p == nullptr) { p = root; } TrieNode *iter = p; while (iter != root) { total_count += iter->count; iter = iter->fail; } } return total_count; } }; int main() { StringPatterns ac_automaton; int n; cin >> n; string pat; for (int i = 0; i < n; ++i) { cin >> pat; ac_automaton.add_pattern(pat); } ac_automaton.build_ACMachine(); string buffer; cin >> buffer; cout << ac_automaton.match_count(buffer) << endl; return 0; }