C++-关于海豚浏览器的一道笔试题

Question

有一个不长于100万的字符串T，还有另外S个（S<100)字符串，这S个串的长度都小于10，现在我们知道T中存在唯一一个子串，是这S个串拼接而成（拼接是首尾相连，S中拼接顺序不一定，中间不存在其它不在S中的串和其它字符），求T中这个子串的位置。
注：S中串拼接顺序是不定的，T中只存在唯一一个这样的子串，所有字符串只包含小写字母。

Answer 1

我想到的一个方法：
1.先用kmp等算法找出S个串在T中的所有起始位置
2.从最小下标开始遍历所有的起始位置，对于每一次遍历：由于当前下标可能是多个串的起始位置，所以需要在无法找到下一个连接串的时候进行回溯，直到找到拼接的子串

Answer 2

对s个串编号，1，2。。。n，kmp找到所有s串在T中所有起始和终止位置并标记下来，然后找一个长串包括从1到n

Answer 3

只想到暴力求解这种方法，但是可以用KMP做字符串匹配。

Answer 4

记这S个字符串的总长度为len， 这S个字符的ascii码的和 为 sum
遍历选取T的 所有长度为len且和为sum 的子串。应该可以过滤掉绝大部分。

再分析这些子串是否为这S个字符串的某种组合形式。不知道这里有没有巧妙的算法。。

Answer 5

S个短字符串编号。需要一个strlen(T)大小的int数组。遍历T的同时在数组中记录每个短字符串出现的位置。最后检查数组中的位置能连起来的就是了。