题意:
找出DNA序列中最长公共子串, 长度不小于3, 否则输出"no significant commonalities". 若等长有多个, 取字典序最小的.
思路:
若是最长公共子串, 每个串中都有, 因此可以只枚举第一个串(由于数据范围小, 先不考虑优化问题).
长度从小到大枚举(若是小的都不满足, 直接跳出判结果; 反之, 则需要一直试探, 找到第一个满足的长度即最大长度)
id 向后移动, 与其他串比较, 若有一个不含有, 则id继续移动. 若都含有, 为可疑答案, 存在ans中(细节注意).
wa了一次, 是循环边界的问题. 要注意.
kmp当然也可以, 但是不必要, 数据规模小.......
阅读全文