狗家新鲜电面

来点自由吗 发表于 2018-10-23 08:27
这题最优的解法应该是跑两次kmp算法，可以参考一下HDU1841 Find the Shortest Common Superstring 的解法

嗯嗯，面试的时候写KMP还是有点凶残。。

1.若A是B的substring或B是A的substring，则返回二者较长的那个
2.否则，求A的后缀与B的前缀的最长公共部分及A的前缀与B的后缀的最长公共部分，取较长的case，这里应该可以用KMP优化，如abcd与cda的结果是abcda，因为cd比a长。

请问楼主怎么做的？也是kmp吗？

dengzeyu147 发表于 2018-10-24 01:42
请问楼主怎么做的？也是kmp吗？

楼主并不会kmp，就直接做的。。
感谢楼上大神们的提示，决定有时间研究一下kmp

LoseYourself 发表于 2018-10-24 01:49
楼主并不会kmp，就直接做的。。
感谢楼上大神们的提示，决定有时间研究一下kmp

暴力姐嘛？有follow up？

LoseYourself 发表于 2018-10-23 08:26
还有有重叠但不能直接拼起来的情况，例如"abcde" "bcfg"

那请问这种情况怎么处理？直接null？

dengzeyu147 发表于 2018-10-24 02:59
暴力姐嘛？有follow up？

是暴力解。没follow up就让写test cases，然后讨论。估计是因为面的seti
没必要纠结这个题啦，只是提供一个参考，感觉不是google家正常的难度

LoseYourself 发表于 2018-10-24 03:09
是暴力解。没follow up就让写test cases，然后讨论。估计是因为面的seti
没必要纠结这个题啦，只是提供 ...

这才是店面的正常难度。~~