python字符串比较的内存限制

Question

我需要编写一个 python 脚本，它可以匹配两个字符串列表并返回列表中最短的和按字典顺序排列的第一个公共部分。列表彼此对应，这意味着 (a1, b1)...(aN, bN)，成对被冻结。规则：a = ['are', 'you', 'how', 'alan', 'dear']b = ['yo', 'u', 'nhoware', 'arala', 'de']result = 'dearalanhowareyou'如果没有这样的字符串连接，那么结果是IMPOSSIBLE：a = ['a', 'b', 'c']b = ['ab', 'bb', 'cc']result = 'IMPOSSIBLE'限制：每个列表中的每个元素只能使用一次每个单独字符串元素的长度 [1;100]最大列表长度为 11所有元素只能成对排列现在，我尝试从shortes 和lexographically 开始考虑它们内部的所有组合和排列。我需要提交它进行测试，在其中一个测试中我得到内存限制条件，限制为 CPU 6 秒和 RAM 1024 MB。

Answer 1

所以，当这种组合是不可能的时，我最终清楚地和早地指定了情况。例如，我们知道回答字符串应该以相同的符号开始和结束。因此，我们可以创建组合，并在进行排列之前检查此类条件。我们也可以检查我们需要检查的片段内所有子串的长度总和是否相等。如果不是，那么我们不进行排列，而是进一步进行

代码

from itertools import chain, combinations, groupby, permutations

import timeit

import collections

import sys

import re

import gc

from functools import reduce

def powerset(iterable):

    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"

    for c in chain(*map(lambda x: combinations(iterable, x), range(0, len(iterable)+1))):

        yield c

def give_permutation(i):

    """

    Yields a permutations of a given combination

    """

    for c in permutations(i):

        yield c

def create_dict(arr):

    """

    Index based dictionary

    """

    dicty = {}

    for i, v in enumerate(arr):

        dicty[i] = v

    return dicty

def tricky_sort(a1, a2):

    """

    Sorts one array and return the second array with index-wise order

    """

    for a in zip(*sorted(zip(a1, a2), key=lambda x: (len(x), x[0]))):

        yield a

def check_complete(starts, ends, array, threshold = 2):

    """

    Checks if combination has both starts and ends

    """

    matches = 0

    for s in starts: 

        if s in array:

            matches += 1

            break

    for e in ends:

        if e in array:

            matches += 1

            break

    return matches == abs(threshold)

def check_match(pairs):

    """

    Checks if answer fits the task

    """

    return ''.join(el[0] for el in pairs) == ''.join(el[1] for el in pairs) 

def algo(a1, a2):

    """

    Checks for the first shortest match between strings

    """

    assert len(a1) == len(a2)

    # fast check for first sorted elements are equal

    if a1[0] == a2[0]:

        return a1[0]

    start_pairs = []

    end_pairs = []

    matches = [] 

    all_pairs = []

    for el1, el2 in zip(a1, a2):

        if el1[0] == el2[0]: start_pairs.append((el1, el2))

        if el1[-1] == el2[-1]: end_pairs.append((el1, el2))

        if el1 == el2: matches.append(el1)

        all_pairs.append(((el1, el2)))

    if len(start_pairs) == 0 or len(end_pairs) == 0: return 'IMPOSSIBLE'

    full_search = 2

    if len(start_pairs) == 1 and len(end_pairs) == 1: 

        full_search = 0

        all_pairs.remove(start_pairs[0])

        all_pairs.remove(end_pairs[0])

    if full_search == 0: 

        if start_pairs[0] == end_pairs[0]:

            return start_pairs[0][0]

        elif start_pairs[0][0] + end_pairs[0][0] == start_pairs[0][1] + end_pairs[0][1]:

            matches.append(start_pairs[0][0] + end_pairs[0][0])

        elif end_pairs[0][0] + start_pairs[0][0] == end_pairs[0][1] + start_pairs[0][1]:

             matches.append(end_pairs[0][0] + start_pairs[0][0])

    lookup_a1 = create_dict([el[0] for el in all_pairs])

    lookup_a2 = create_dict([el[1] for el in all_pairs])

    range_list = list(range(len(all_pairs)))

    del a1, a2

    clean_combs = []

    sorted_names = []

    if len(range_list) > 0:

        for i in powerset(range_list):

            if len(i) > 0 :

                if full_search == 2:

                    if check_complete(start_pairs, end_pairs, [all_pairs[index] for index in i]) and \

                            sum([len(all_pairs[index][0]) for index in i]) == sum([len(all_pairs[index][1]) for index in i]):

                        arr1_str = ''.join(lookup_a1[index] for index in i)

                        arr2_str = ''.join(lookup_a2[index] for index in i)

                        if len(arr1_str) == len(arr2_str):

                            if reduce(lambda x, y: x + y, sorted(arr1_str)) == reduce(lambda x, y: x + y, sorted(arr2_str)):

                                clean_combs.append(i)

                else:

                    clean_combs.append(i)

        if len(clean_combs) > 0:

            for i in clean_combs:

                for combination in give_permutation(i):

                    if full_search == 2:

                        if lookup_a1[combination[0]][0] != lookup_a2[combination[0]][0] or \

                            lookup_a1[combination[-1]][-1] != lookup_a2[combination[-1]][-1]:

                                continue

                        if check_match([all_pairs[index] for index in combination]):

                            matches.append(''.join(all_pairs[index][0] for index in combination))

                    elif full_search == 0:

                        option = start_pairs + [all_pairs[index] for index in combination] + end_pairs

                        if check_match(option):

                            matches.append(''.join(el[0] for el in option))

    if len(matches) > 0:

        matches = sorted(matches, key=lambda x: (len(x), x[0]))

        return matches[0]    

    return 'IMPOSSIBLE'

def string_processor(string):

    """

    Splits string by integers and returns arrays with only letters inside

    """

    arr = ' '.join(re.findall(r'[0-9|a-zA-Z]+', string.replace(r'\n', ' '))).strip()

    all_ints = re.findall(r'[0-9]+', arr)

    arr = re.compile(r'[0-9]+').split(arr)

    arr = [re.findall(r'[a-zA-Z]+', a) for a in arr if len(a) > 0]

    for r in arr:

        yield r

def substring_processor(substring, shift = 0):

    """

    Returns two array with the first and the second sequences

    """

    arr1 = []

    arr2 = []

    for i in range(0, len(substring), 2):

        yield substring[i + shift]

def string_arr(arr1, arr2):    

    for t in tricky_sort(arr1, arr2):

        yield t

def process_file(file):

    """

    Iterates over all sequences in a file

    """

    case_counter = 0

    for sub in string_processor(file):

        case_counter += 1

        str1, str2 = string_arr(substring_processor(sub), substring_processor(sub, shift = 1))

        print('Case %s: ' %  str(case_counter) + algo(str1, str2) + '\n')

def read_files():

    """

    Takes input data

    """

    input_string = ''

    for f in sys.stdin:

        input_string += f

    process_file(input_string)

read_files()

Answer 2

我认为您可以生成正确的子字符串（所有这些子字符串，在我看来，在生成时间您无法真正确定它们是否都是“按字典顺序”首先和最短的），如下所示：

from itertools import permutations

from pprint import pprint

a = ['are', 'you', 'how', 'alan', 'dear']

b = ['yo', 'u', 'nhoware', 'arala', 'de']

c = zip(a,b)

m = []

for p in permutations(c):

  stra = ""

  strb = ""

  for t in p:

    stra += t[0]

    strb += t[1]

    if stra == strb: m.append(stra)

pprint(m)

然后继续检查是否m仍然为空或以任何笨拙的方式选择“第一个”项目，因为无论如何该列表将是一个简短的列表。就像按字母顺序排序，然后选择最排序的一个：

if len(m) == 0: w = "IMPOSSIBLE"

else:

  w = m[0]

  for x in sorted(m):

    if len(x) < len(w): w = x

print(w)