查找匹配模式的最短句子的算法

Question

我在这里有一个问题，我试图解决。

该程序被给予包含以下字符的文本文件：A - Z，A - Z，0 - 9，句号和空间（。）。文本文件中的单词纯粹由a-z，A-Z和0-9组成。该计划收到几个查询。每个查询由文件中已存在的一组完整单词组成。程序应该从文件中返回所有单词出现的最小短语（以任何顺序）。如果有这样的短语，返回第一个。

这里是一个例子。让我们假设该文件包含：

Bar is doing a computer science degree. Bar has a computer at home. Bar is now at home. 

查询1：

Bar computer a 

响应：

Bar has a computer 

查询2：

Bar home 

响应：

home. Bar 

我认为这个解决方案的。对于查询1，Bar首先被搜索，并且Bar的所有三次出现都被组合为列表。列表中的每个节点还包含最小短语的起始位置和总长度。因此，它会像

1点“酒吧，0,1”【查询，开始posn处，总长度。 对于第二个和第三个节点类似。

下一台计算机被搜索。计算每次出现Bar的计算机的最小距离。其它节点

接着

第一节点“酒吧计算机”，0，5

第二节点“酒吧电脑”，7,4等“a”被搜索。搜索必须从每个节点提到的起始位置开始，并且必须左右移动直到找到该单词为止，因为顺序不重要。发生的最小值必须被选择。

是在正确的轨道这个解决方案？我觉得这样做，我必须警惕许多情况下，可能会有一个更简单的解决方案。

如果字是独一无二的，它成为TSP的变种？

Answer 1

TSP不是考虑这个问题的好方法。设n是文本的长度，m是查询的长度;假设n> m。幼稚溶液

best = infinity 
for i = 1 to n 
    for j = i to n 
    all_found = true 
    for k = 1 to m 
     found = false 
     for l = i to j 
     if text[l] == query[k] 
      found = true 
     all_found = all_found || found 
    if all_found && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

已经多项式时间在为O（n 3 米）为界长度的话。现在让我们优化。

首先，通过散列集提升内部循环。

best = infinity 
for i = 1 to n 
    for j = i to n 
    subtext_set = {} 
    for l = i to j 
     subtext_set = subtext_set union {text[l]} 
    all_found = true 
    for k = 1 to m 
     all_found = all_found && query[k] in subtext_set 
    if all_found && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

的运行时间是现在为O（n ），或者为O（n log n）的，如果我们使用二叉树来代替。

现在注意到当上限增加1时重新计算subtext_set是浪费的。

best = infinity 
for i = 1 to n 
    subtext_set = {} 
    for j = i to n 
    subtext_set = subtext_set union {text[l]} 
    all_found = true 
    for k = 1 to m 
     all_found = all_found && query[k] in subtext_set 
    if all_found && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

我们在为O（n 米）。现在，当subtext_set只增加一个元素时，重新检查整个查询似乎很浪费：为什么我们不检查那一个，并记住我们必须去多少？

query_set = {} 
for k = 1 to m 
    query_set = query_set union {query[k]} 
best = infinity 
for i = 1 to n 
    subtext_set = {} 
    num_found = 0 
    for j = i to n 
    if text[l] in query_set && text[l] not in subtext_set 
     subtext_set = subtext_set union {text[l]} 
     num_found += 1 
    if num_found == m && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

我们在为O（n ）。到O（n）需要一些见解。首先，让我们来看看每个子多少查询词包含的例子

text = Bar has a computer at home. Bar 
     1 2 3 4  5 6  7 
query = Bar computer a 

# j 1 2 3 4 5 6 7 
i +-------------- 
1 | 1 1 2 3 3 3 3 
2 | 0 0 1 2 2 2 3 
3 | 0 0 1 2 2 2 3 
4 | 0 0 0 1 1 1 2 
5 | 0 0 0 0 0 0 1 
6 | 0 0 0 0 0 0 1 
7 | 0 0 0 0 0 0 1 

此矩阵具有非增柱和非减行，并普遍认为是真实的。我们希望遍历值为m的条目的底部，因为进一步对应于更长的解决方案。该算法如下。如果当前的i，j具有所有查询词，则增加i;否则，增加j。

随着我们目前的数据结构，增加j是好的，但增加我不是，因为我们的数据结构不支持删除。当一个查询词的最后一个副本消失时，我们需要保留一个多组并且减少num_found。

best = infinity 
count = hash table whose entries are zero by default 
for k = 1 to m 
    count[query[k]] = -1 
num_found = 0 
i = 1 
j = 0 
while true 
    if num_found == m 
    if j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 
    count[text[i]] -= 1 
    if count[text[i]] == -1 
     num_found -= 1 
    i += 1 
    else 
    j += 1 
    if j > n 
     break 
    if count[text[j]] == -1 
     num_found += 1 
    count[text[j]] += 1 

我们已经到达O（n）。最后一个渐近相关的优化是通过仅为查询中的元素存储计数来将额外的空间使用从O（n）减少到O（m）。我会把那个作为练习。 （另外，必须更加小心地处理空查询。）

Answer 2

对于这样的问题，我建议使用Suffix Trees。