合并/放弃重叠单词

Question

我想合并相似的字符串（单词）（字符串在其他字符串中）。在

 word
 wor 
 words
 wormhole
 hole    

会使：

^{pr2}$

由于wor与：word，words，wormhole-wor重叠；
word与以下内容重叠：words-word被丢弃；
hole与以下内容重叠：wormhole-hole被丢弃；
但是words，wormhole没有重叠，所以它们会保留下来。
我该怎么做？在

编辑
我的解决方案是：

while read a
do  
   grep $a FILE | 
   awk 'length > m { m = length; a = $0 } END { print a }'
done < FILE | 
sort -u

但我不知道它是否会给大数据集带来麻烦。在

Answer 1

有了足够长的单词列表，单词上的任何嵌套循环都将非常缓慢。我就是这样做的：

use strict;
use warnings;

use File::Slurp 'read_file';
chomp( my @words = read_file('/usr/share/dict/words') );

my %overlapped;
for my $word (@words) {
    $word =~ /(.*)(?{++$overlapped{$1}})(*FAIL)/;
    --$overlapped{$word};
}

print "$_\n" for grep ! $overlapped{$_}, @words;

也许可以通过Darshan Computing提出的从最长到最短处理单词的建议加以改进。在

Answer 2

在Ruby中：

list = %w[word wor words wormhole]

list.uniq
.tap{|a| a.reverse_each{|e| a.delete(e) if (a - [e]).any?{|x| x.include?(e)}}}

Answer 3

在我看来，把单词从最长到最短排序，我们就可以一步一步地浏览排序后的列表一次，只与保留的单词匹配。我不擅长算法分析，但这对我来说是有意义的，我认为性能会很好。它似乎也起作用，假设保留单词的顺序无关紧要：

words = ['word', 'wor', 'words', 'wormhole', 'hole']
keepers = []

words.sort_by(&:length).reverse.each do |word|
  keepers.push(word) if ! keepers.any?{|keeper| keeper.include?(word)}
end

keepers
# => ["wormhole", "words"]

如果保留单词的顺序很重要，那么很容易修改这个来解释这个问题。一种选择就是：

^{pr2}$