LCS 问题在于 NPCompllete 是一个数量不限的字符串 N. 意思是, 没有已知的多元算法能够解决这个问题。 也意味着您可以放弃 DP 解决方案 : p

这里可以连接到一种通勤方法, 以接近多个字符串的 LCS 。

http://www.aaai.org/ocs/index.php/AAAI/AAI10/paper/download/1559/2197

您可以在 O( Nlog( N)) 时间( N是序列的合并长度)下做这项工作, 方法是用滚动散列进行类似二进制搜索 。

请注意,尽可能长的共同序列的长度是最小序列的长度,即 smallestLength 。

初始化 :

• assume the length of the longest common subsequence (which we call a) is a = smallestLength/2

算法 :

• iteration_number += 1
• scan through all lists (in parallel if you want!) and perform a rolling hash; this will generate len(list)-(a-1) hashes for each list
• insert all the hashes into a set data structure (one set per list) to achieve O(1) lookup time
• check to see if any of the hashes collide (take the intersection of all the sets): if there are one or more collisions, manually confirm that there is an a-length subsequence common subsequence in those positions, since the hashes might be wrong (though this will never occur in practice if you choose a sufficiently fine hash)
• did you find a shared sequence?
  • if you find such a sequence, repeat the above steps, but increase the assumed length like you would in binary search (add smallestlength/2**iteration_number)
  • if you don t find such a sequence, repeat the above steps, but decrease the assumed length like you would in a binary search (subtract smallestlength/2**iteration_number)

Python3的解决方案是:

#Uses python3
import sys
def calc_cache_pos(strings, indexes):
    factor = 1
    pos = 0
    for s, i in zip(strings, indexes):
        pos += i * factor
        factor *= len(s)
    return pos

def lcs_back(strings, indexes, cache):
    if -1 in indexes:
        return ""
    match = all(strings[0][indexes[0]] == s[i]
                for s, i in zip(strings, indexes))
    if match:
        new_indexes = [i - 1 for i in indexes]
        result = lcs_back(strings, new_indexes, cache) + strings[0][indexes[0]]
    else:
        substrings = [""] * len(strings)
        for n in range(len(strings)):
            if indexes[n] > 0:
                new_indexes = indexes[:]
                new_indexes[n] -= 1
                cache_pos = calc_cache_pos(strings, new_indexes)
                if cache[cache_pos] is None:
                    substrings[n] = lcs_back(strings, new_indexes, cache)
                else:
                    substrings[n] = cache[cache_pos]
        result = max(substrings, key=len)
    cache[calc_cache_pos(strings, indexes)] = result
    return result

def lcs(strings):
        if len(strings) == 0:
        return ""
    elif len(strings) == 1:
        return strings[0]
    else:
        cache_size = 1
        for s in strings:
            cache_size *= len(s)
        cache = [None] * cache_size
        indexes = [len(s) - 1 for s in strings]
        return (lcs_back(strings, indexes, cache))
if __name__ ==  __main__ :
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    an = data[0]
    data = data[1:]
    a1 = data[:an]
    data = data[an:]
    bn = data[0]
    data = data[1:]
    b1 = data[:bn]
    data = data[bn:]
    cn = data[0]
    data = data[1:]
    c1 = data[:cn]
    a =   
    for i in a1:
        a = a + i
    b =   
    for i in b1:
        b = b + i
    c =   
    for i in c1:
        c = c + i
    print(lcs([a, b, c]))

这里读取 3+ 数组的输入, 每个字符组后面有一个空格。 < 坚固> 在每一数组输入数组大小之前, 每个数组输入 。 输入

< 强度 > INPUT :

8 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8

a b a a a c b b b b b b

6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

d c a b a b a

6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6

b b a a c a a a

<% 1>/% 1 < profession > :

baa( baa)

仅供参考:

from difflib import SequenceMatcher


def lcs_of_2(a, b):
    """
    get longest common string
    :param a:
    :param b:
    :return:
    """
    match = SequenceMatcher(None, a, b).find_longest_match(0, len(a), 0, len(b))
    return a[match[0]: match[0] + match[2]]


def lcs_of_list(*args):
    """
    get longest common string of list
    :param args:
    :return:
    """
    if len(args) == 2:
        return lcs_of_2(args[0], args[1])
    first = args[0]
    remains = args[1:]
    return lcs_of_2(first, lcs_of_list(*remains))


if __name__ ==  __main__ :
    a =  abcdef 
    b =  abbbbabcdeffff 
    c =  bcdefff 
    print(lcs_of_list(a, b, c))

结果:

bcdef