如何搜索以同一陣列中的其他單詞開頭和結尾的單詞？

Question

我有一個數組中的單詞的長列表。有些短暫，有些長。我想過濾掉那些以數組中的單詞開頭的單詞（這個「前綴」單詞的長度可以設置爲3個字符），並且同時以它的單詞結尾。

假設第一個詞是'carport'。現在，如果陣列中存在'car'和'port'，我會得到一個匹配。但如果這個詞是'carlsberg'，我不會得到一個匹配（因爲'lsberg'可能不會是數組中存在的單詞）。

結果最好會出現爲「前綴詞，後綴詞，整個詞」。

我會考慮使用任何語言，可以讓我這樣做，雖然我主要是一個JavaScript的人自己。

Answer 1

那麼，在JavaScript中幼稚的實施方法是這樣的：

function triples(words) { 
    var result = new Array(); 
    for(var i=0; i<words.length; i++) { 
     for(var j=0; j<words.length; j++) { 
      var k = words.indexOf(words[i] + words[j]); 
      if(k != -1) { 
       result.push([words[i], words[j], words[k]]); 
      } 
     } 
    } 
    return result; 
} 

在其當前形式的功能需要的所有單詞作爲參數陣列，並返回包含所找到的字三元數組的數組（第一元素是前綴，第二個元素是後綴，第三個元素是組合詞）。

Answer 2

事情是這樣的：

#!/usr/bin/perl 

use strict; 
use warnings; 

my @candidates=qw(carport Carsburg butterfly 
       buttercup Christmas wishlist carpface flyface buttface); 
my @arr=<DATA>; 
chomp @arr; 

for my $i (3..6) { 
    foreach my $j (@candidates) { 
     my ($fp,$lp)=($1,$2) if ($j=~/(^.{$i})(.*$)/); 
     if($fp && $lp) { 
      my @hit1=grep(/^$fp/,@arr); 
      my @hit2=grep(/$lp$/,@arr); 
      print "candidate: $j\n start= @hit1 end= @hit2\n=====\n" 
       if (scalar @hit1 && scalar @hit2); 
     } 
    } 
} 

__DATA__ 
car 
port 
wish 
list 
Christ 
mas 
butter 
cup 
fly 
face 
butt 

輸出：

candidate: carport 
start= car end= port 
===== 
candidate: flyface 
start= fly end= face 
===== 
candidate: wishlist 
start= wish end= list 
===== 
candidate: buttface 
start= butter butt end= face 
===== 
candidate: butterfly 
start= butter end= fly 
===== 
candidate: buttercup 
start= butter end= cup 
===== 
candidate: Christmas 
start= Christ end= mas 

Answer 3

我不知道如果一個trie會有所幫助，看到What is the most common use of the 「trie」 data structure?。

Perl有幾個模塊來構建它們：

• Tree::Trie
• Text::Trie

別的東西，聽起來有點像這將是一個起點是Ruby's Abbrev模塊：

#!/usr/bin/env ruby 

require 'abbrev' 
require 'pp' 

pp %w[car port carport carlsberg].abbrev 
# >> {"por"=>"port", 
# >> "po"=>"port", 
# >> "p"=>"port", 
# >> "carpor"=>"carport", 
# >> "carpo"=>"carport", 
# >> "carp"=>"carport", 
# >> "carlsber"=>"carlsberg", 
# >> "carlsbe"=>"carlsberg", 
# >> "carlsb"=>"carlsberg", 
# >> "carls"=>"carlsberg", 
# >> "carl"=>"carlsberg", 
# >> "car"=>"car", 
# >> "port"=>"port", 
# >> "carport"=>"carport", 
# >> "carlsberg"=>"carlsberg"} 

Answer 4

這裏我SA Perl的解決方案，O(n + 2m)：

use warnings; 
use strict; 
use Data::Dumper; 

my @words = qw(car carport carlsberg cartographer airport photographer); 

my @ends = qw(car port air grapher); 

my $ends_re = join '|' => @ends; 

my @matches = map {/^($ends_re).*($ends_re)$/ ? [$1, $_, $2] :()} @words; 

print Dumper \@matches; 

打印：

$VAR1 = [ 
     [ 
     'car', 
     'carport', 
     'port' 
     ], 
     [ 
     'car', 
     'cartographer', 
     'grapher' 
     ], 
     [ 
     'air', 
     'airport', 
     'port' 
     ] 
    ]; 

Answer 5

我會做這樣的事情：

<?php 

    $words = array('experts', 'exchange', 'expert', 'sexchange'); 

    // build trie 
    $t = array(); 
    foreach ($words as $word) 
    { 
     $n = &$t; 
     for ($i = 0; $i < strlen($word); ++$i) 
     { 
      $c = $word[$i]; 

      if (!isset($n[$c])) $n[$c] = array(); 

      $n = &$n[$c]; 
     } 

     $n['.'] = true; 
    } 

    $word = 'expertsexchange'; 

    $n = $t; 
    for ($i = 0; $i < strlen($word); ++$i) 
    { 
     $c = $word[$i]; 

     if (isset($n['.'])) 
     { 
      $o = $t; 
      for ($j = $i; $j < strlen($word); ++$j) 
      { 
       $d = $word[$j]; 
       if (!isset($o[$d])) break; 
       $o = $o[$d];      
      } 

      # found match 
      if ($j == strlen($word) && isset($o['.'])) 
      { 
       echo substr($word, 0, $i).",".substr($word,$i).",".$word."\n"; 
      } 
     } 

     if (isset($n[$c])) 
     { 
      $n = $n[$c]; 
     } 
     else 
      break; 
    } 
?> 

Results: 

expert,sexchange,expertsexchange 
experts,exchange,expertsexchange 

我寫在了當場，所以它可能無法正常工作完全正確。但是，這個想法是建立一個前綴樹，並通過它。每當你找到一個前綴（用'。'表示），從樹的頂部再次繼續，看看你是否可以從這一點找到後綴。這假定你不需要前綴和後綴之間的任何東西。