后缀数组处理多字符串公共子串总结

迈不过友情╰ 2022-08-24 04:19 204阅读 0赞

关于后缀数组的学习可以参考：[后缀数组学习小记 (模板) - whyorwhnt的专栏][_ - whyorwhnt]

个人经验：对单个字符串问题求个数需要枚举，求长度可以利用二分

公共子串：如果字符串L同时出现在字符串A和字符串B中，则称字符串L是字符串A和字符串B的公共子串。

与子序列不同的是，子序列可以断续，通常用dp解决，子串要求连续。

# 最长公共子串问题的后缀数组解法 #

后缀数组可以处理一类公共子串问题，以下方法分析摘自：[最长公共子串问题的后缀数组解法 - BYVoid][- BYVoid]

回顾一下后缀数组，SA\[i\]表示排名第i的后缀的位置，Height\[i\]表示后缀SA\[i\]和SA\[i-1\]的最长公共前缀(Longest Common Prefix,LCP)，简记为Height\[i\]=LCP(SA\[i\],SA\[i-1\])。连续的一段后缀SA\[i..j\]的最长公共前缀，就是H\[i-1..j\]的最小值，即LCP(SA\[i..j\])=Min(H\[i-1..j\])。

求N个串的最长公共子串，可以转化为**求一些后缀的最长公共前缀的最大值**，这些后缀应分属于N个串。具体方法如下：

设N个串分别为S1,S2,S3,...,SN，首先建立一个串S，把这N个串用不同的分隔符连接起来。S=S1\[P1\]S2\[P2\]S3...SN-1\[PN-1\]SN，P1,P2,...PN-1应为**不同**的N-1个不在字符集中的字符，作为分隔符(后面会解释为什么)。

接下来，求出字符串S的后缀数组和Height数组，可以用倍增算法，或DC3算法。

然后二分枚举答案A，假设N个串可以有长度为A的公共字串，并对A的可行性进行验证。如果验证A可行，A'(A'<A)也一定可行，尝试增大A，反之尝试缩小A。最终可以取得A的最大可行值，就是这N个串的最长公共子串的长度。可以证明，尝试次数是O(logL)的。

于是问题就集中到了，如何验证给定的长度A是否为可行解。方法是，找出在Height数组中找出连续的一段Height\[i..j\]，使得i<=k<=j均满足Height\[k\]>=A，并且i-1<=k<=j中，SA\[k\]分属于原有N个串S1..SN。如果能找到这样的一段，那么A就是可行解，否则A不是可行解。

具体查找i..j时，可以先从前到后枚举i的位置，如果发现Height\[i\]>=A，则开始从i向后枚举j的位置，直到找到了Height\[j+1\]<A，判断\[i..j\]这个区间内SA是否分属于S1..SN。如果满足，则A为可行解，然后直接返回，否则令i=j+1继续向后枚举。S中每个字符被访问了O(1)次，S的长度为N*L+N-1，所以验证的时间复杂度为O(N*L)。

到这里，我们就可以理解为什么分隔符P1..PN-1必须是不同的N-1个不在字符集中的字符了，因为这样才能保证S的后缀的公共前缀不会跨出一个原有串的范围。（否则下一个字符串的部分前缀也会成为公共的部分）

# 题目小结 #

## 两个字符串 ##

[POJ 2774 Long Long Message+Hdu 1403 Longest Common Substring (后缀数组 最长公共子串) - whyorwhnt的专栏][POJ 2774 Long Long Message_Hdu 1403 Longest Common Substring _ _ - whyorwhnt]

[URAL 1517 Freedom of Choice (后缀数组 输出两个串最长公共子串) - whyorwhnt的专栏][URAL 1517 Freedom of Choice _ _ - whyorwhnt]

[POJ 3729 Facer’s string (后缀数组 两串后缀的LCP为K的对数) - whyorwhnt的专栏][POJ 3729 Facer_s string _ _LCP_K_ - whyorwhnt]

## 多个字符串 ##

[POJ 1226 Substrings (后缀数组 n个串的最长公共子串) - whyorwhnt的专栏][POJ 1226 Substrings _ n_ - whyorwhnt]

[Poj 3294 Life Forms (后缀数组 在n个串中出现k次的最长公共子串并输出) - whyorwhnt的专栏][Poj 3294 Life Forms _ _n_k_ - whyorwhnt]

[Poj 3080 Blue Jeans + Hdu 2328 Corporate Identity (后缀数组 字典序最小的最长公共子串) - whyorwhnt的专栏][Poj 3080 Blue Jeans _ Hdu 2328 Corporate Identity _ _ - whyorwhnt]

[spoj 220 Relevant Phrases of Annihilation (后缀数组 每个串中都至少出现两次的不重叠最长子串) - whyorwhnt的专栏][spoj 220 Relevant Phrases of Annihilation _ _ - whyorwhnt]

[_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/32933319
[- BYVoid]: https://www.byvoid.com/blog/lcs-suffix-array
[POJ 2774 Long Long Message_Hdu 1403 Longest Common Substring _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9772517
[URAL 1517 Freedom of Choice _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/34075603
[POJ 3729 Facer_s string _ _LCP_K_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9821377
[POJ 1226 Substrings _ n_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9786455
[Poj 3294 Life Forms _ _n_k_ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9812859
[Poj 3080 Blue Jeans _ Hdu 2328 Corporate Identity _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/9857911
[spoj 220 Relevant Phrases of Annihilation _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/34116147