字符串算法三连击

Hash算法

如何快速判断两个字符串 相等？

如果两个字符串被同一个函数 映射到相同的值，也就是 ，那么有可能

仔细地选择 ，可以使得 的概率很大，从而完成快速判断

其中 取质数（当 不是质数的时候降低碰撞概率），例如 。
其中 可以取：

• ，用 位无符号自然溢出，计算速度快
• 级别的质数

当 取 级别质数的时候，应多取几个 以获得更高的正确率（只取一个是不行的）

Hash快速计算

给定一个字符串 ，要求在 时间内快速获得任意一个子串的 函数

设 ，那么记：

则 的 函数就是：

预处理 , ， 计算子串 函数

利用Hash求LCP

LCP：最长公共前缀

多次询问一个字符串 的两个后缀 的 LCP，要求每次询问 时间

解法:

多次询问一个字符串 S 的两个后缀 的 LCP，要求每次询问 时间。

二分长度，问题转化成判断一个字符串的两个子串是否相等。

利用预处理的 hash 函数解决，判断相等需要 时间，加上二分共 时间。（更好的做法：后缀数组

利用 hash 比较子串字典序

多次询问一个字符串 S 的两个子串 的字典序，要求每次询问 时间

先求出这两个子串对应后缀的 LCP，如果这个长度不小于 ，那说明这两个字符串相等

如果这个长度不小于 ，说明一个子串是另一个子串的前缀，此时长的字符串字典序靠后

否则判断这个最长公共前缀的后一个字符，哪个字符串对应的后面的字符大说明哪个字符串字典序靠后。（可以利用这个 构造后缀数组）

应用

大....大....大水题？

CTSC 2014 企鹅 QQ

题意

给 个字符串，如果两个字符串只有一个位置的字符不相同，那么称这两个字符串是相似的。

字符串的长度都相等，并且字符串两两不同。求一共有多少对相似字符串。

，时间限制 秒

题解

如果两个字符串是相似的，那么去掉某个相同位置的字符后这两个字符串相等，去掉其他相同位置的字符后这两个字符串不等

枚举删去字符的位置，然后用 hash 的方法计算相等的字符串对数. 对 hash 值构建桶或者对 hash 值排序后统计均可

HNOI 2014 抄卡组

题意

给 个带有通配符 的字符串，通配符可以匹配任意多个字符，问这 个字符串是否可以代表同一个字符串。

题解

如果所有字符串都有通配符，判断前缀和后缀是不是相等就可以了。把所有字符串到通配符前的前缀拿出来，按照长度排序，Hash 判断，后缀同理。

如果所有字符串都不含有通配符， Hash 判断是不是一个字符串。否则拿出一个不含通配符的字符串，如果有其他不含通配符的字符串跟它不相等直接判断出来即可。问题转化为判断一个含有通配符的串是否能等于某个不含有通配符的串，特殊处理前缀和后缀之后，贪心处理中间通配符隔开每一段，跟模版串匹配，顺次匹配成功则答案为可以，否则答案为不可以

End