继KB用TRIE树、XZY用DFS将此题在5ms内AC后,本人也跟风用KMP来AC了此题,耗时258ms。我真是太弱了。垃圾地我竟然写了72行!而且还是最慢的。。。

题意:用给定的一些字符串拼凑新的字符串,给定的字符串的可被拼凑的最长前缀的长度是多少?有约200个长度10以内的给定字符串和一个长度200000以内的目标串。字符串可以重复使用。

思路:此题思路较多:

1.XZY:考虑到字符串真正用到的部分较少,匹配时失配几率较大,所以可以使用搜索去逼近并达到最长前缀。

XZY的做法

2.KB:采用TRIE树,应该为本题的正解,但是代码量大,在数据水和常数大的局限下速度也不如搜索快,次解法可以自行百度。

KB的做法

3.我:注意到O(200×200000×k)的复杂度是可行的,所以可以对每一个小字符串对原数组进行KMP匹配,求得每个字符串可以覆盖目标串的部分,再用动态规划求出目标串的最长前缀无重叠覆盖面积。虽然很垃圾,但是AC还是没有问题的。