Counting подстроки из заданного набора слов

Question

у меня есть набор строк (словарь) и строка T, я должен подсчитать, сколько раз я могу построить T из слов в моем словаре

, например

словарь содержит: hello world llo he

и струнный T "HelloWorld"

выход должен быть 2, так как "hellowold" может быть построен из здравствуйте + мир, он + LLO + мир

Есть ли эффективный алгоритм для этого?

Answer 1

Вот быстрое внедрение в Python:

from collections import defaultdict 

def count_constructions(words, string): 
    # First we're going to make a map with 
    # positions mapped to lists of words starting 
    # at that position in the string 
    words_at_index = defaultdict(list) 
    for word in words:  
     i = string.find(word) 
     while i >= 0: 
      words_at_index[i].append(word) 
      i = string.find(word, i + 1) 
    # I know there's a more pythonic way to do this, 
    # but the point here is to be able to inc count within 
    # the auxilliary function 
    count = [ 0 ] 

    # This will find all of the ways to cover the remaining string 
    # starting at start 
    def recurse(start): 
     for w in words_at_index[start]: 
      # w matches from string[start] to string[next_start] 
      next_start = start + len(w) 
      # see if we've covered the whole thing.   
      if next_start == len(string): 
       count[0] += 1 
       # we could also emit the words forming the string here 
      else: 
       # otherwise, count the times we can cover it from 
       # next_start on 
       recurse(next_start) 

    recurse(0) 
    return count[0] 


dictionary = [ 'hello', 'world', 'llo', 'he' ] 
word = "helloworld" 

print(count_constructions(dictionary, word)) 

Answer 2

Я бы начал с получения подмножества из вашего словаря, содержащего только слова, которые могут быть частью слова, которое вы ищете. Затем, с остальными словами, которые вы можете выполнить с помощью backtrack, он не должен использовать слишком много ресурсов, так как набор, в который вы будете запускать backtrack, будет очень маленьким.