一 05
这是一个经典的求多个串的最长公共子串的问题。如果设字符串的个数为N，每个串最大的长度为L，则这道题有时间复杂度为O(N*L^4),O(N*L^3),O(N*L^2)和O(N*L)的算法。
最简单的想法是对于某一个串，取出它的所有的L^2个子串，然后再在其他每一个字符串中进行朴素的匹配，很显然是O(N*L^4)。如果生搬硬套地用KMP，那么是O(N*L^3)的算法。仔细一想，其实枚举所有的L^2个子串是完全没有必要的，仅仅取出某一个串的L个后缀，对于每一个后缀在其他的所有串中部分匹配即可，用朴素匹配就是O(N*L^3)，用KMP就是O(N*L^2)，可以通过所有测试点。
另外，如果用Trie，把每个串的所有后缀全部插入Trie树中，标记每个节点所属的原串。找到最深的属于所有串的节点，它的最大深度就是最长公共前缀，时间复杂度依然是O(N*L^2)，但是会有一点超时。
对于这道题来说，对某个串的每个后缀进行部分模式匹配，O(N*L^2)的算法就可以了。如果想进一步探究，恐怕就要用到后缀树了，广义后缀树求最长公共子串有O(N*L)的算法，我还没有学过，现在正在苦读中。
下面是我的O(N*L^2)的KMP。
Recent Comments