字符串算法

字符串算法

字符串算法分很多种，每次编程比赛，字符串必出一道题，所以集中花一些时间在 “字符串的处理” 算法上,总不会吃亏，其具体体现在以下几个方面：

• 字符串 hash

• tire tree

• KMP

• AC自动机

• 扩展KMP

• 后缀数组

• manache

字符串 hash

核心代码如下

哈希表基本原理是使用一个下标范围比较大的数组A来存储元素，设计一个函数h,对于要存储的线性表的每个元素node,取一个关键字key,算出一个函数值h(key),把h(key)作为数组下标，用a[h(key)]这个数组单元来存储node.这样做有很大一个弊端，那就是很有可能不同的元素，计算的函数值相同，为避开这样，博客上也有大佬经过实践得出，h（key）=(key*131)mod INf,INF为一个极大的素数;这样做目前是最好的。

例题：给出n个不同的正整数a[1]a[n],他们的值在11000000之间。在给定一个整数X,编程计算这样数对个数(a[i],a[j]),1

分析：在比赛时，如果用双重循环查找判断，肯定超时。用哈希表处理，定义a[x]表示x这个数在数列中是否存在，然后只需要扫描1~x/2，若数字存在，则只需要看x减去这个数的结构是否存在即可；

代码如下

值得注意的注意的地方 ：

就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值

Hash主要作用是状态判重

搜索题目中的去重处理

字符串重复判断处理

字典树

定义：又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，常常用来保存字符串集合。如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。如下图就是一个trie树，表示的字符串集合为，每个单词的结束位置对应一个“单词节点”。反过来，从根节点到每个单词结点的路径上所有字母链接而成的字符串就是该结点对应的字符串。

在程序上，将根结点编号为0，然后用一个数组来保存每个结点的所有子节点，用下标直接存取。

节点 路径

起始节点 t,a,i

t,a,i o,e,n

to,te,in a,d,n,m

tea,ted,ten,inm 无

tire tree 三性质：

• 根结点不包含字符，除根结点外每一个结点都只包含一个字符

• 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串

• 每个结点的所有子结点包含的字符都不相同

tire tree 实现过程 ：

• 根据给定单词预处理建树。

• 单词结尾处结点上添加相应标记

• 根据要求，查询或者插入相关字符串

tire tree 查找 :

• 每次从根结点开始一次搜索

• 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索

• 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索

• 迭代过程

• 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找

建树代码如下 ：

树的查询代码如下 ：

例题：第一行一个整数 n，表示班上人数。接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。第 n+2 行一个整数 m，表示教练报的名字。接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 50）。对于每个教练报的名字，输出一行。如果该名字正确且是第一次出现，输出“OK”，如果该名字错误，输出“WRONG”，如果该名字正确但不是第一次出现，输出“REPEAT”。（均不加引号）

分析：将输入结果转化为树，查询节点是否和对应的名字匹配

题解代码如下 :

时间复杂度 ：

插入N个单词的时间复杂度为：NK

查询M个单词的时间复杂度为：MK

以上是字符串算法用的最多的两种，其他几类博客上也有所介绍，这里只对两种做以分析和讲解，希望对读者有所帮助