Comment rechercher des mots commençant et se terminant par d'autres mots du même tableau?

Question

J'ai une longue liste de mots dans un tableau. Certains courts, d'autres longs. Je voudrais filtrer ces mots qui commencent par un mot du tableau (la longueur de ce mot "préfixe" peut être fixé, disons, à 3 caractères) et qui en même temps se termine par un mot.

Disons que le premier mot est «carport». Maintenant, si 'voiture' et 'port' existent aussi dans le tableau, j'obtiendrais une correspondance. Mais si le mot est "carlsberg", je n'aurais pas de correspondance (puisque "lsberg" ne serait probablement pas un mot existant dans le tableau). Les résultats apparaîtront de préférence sous la forme "préfixe mot, suffixe mot, mot entier".

J'envisagerais d'utiliser n'importe quel langage qui peut me faire faire cela, bien que je sois moi-même surtout un type JavaScript.

Answer 1

Eh bien, la mise en œuvre naïve en JavaScript serait comme ceci:

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; 
} 

La fonction sous sa forme actuelle exige que le tableau de tous les mots en tant que paramètre et retourne un tableau de tableaux contenant les triplets de mots trouvés (premier élément étant le préfixe, le deuxième élément étant le suffixe, le troisième élément étant le mot combiné).

Answer 2

Quelque chose comme ceci:

#!/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 

Sortie:

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

Je me demande si un trie aiderait, voir What is the most common use of the “trie” data structure?.

Perl dispose d'un module de couple pour les construire:

• Tree::Trie
• Text::Trie

Quelque chose d'autre qui sonne un peu comme ce serait un point de départ est le module 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

Ici je sa solution Perl qui est 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; 

impressions:

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

Answer 5

je ferais quelque chose comme:

<?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 

Je l'ai écrit sur place, donc il ne fonctionne pas tout à fait exact . Mais l'idée est de construire un arbre de préfixe et de le parcourir. Chaque fois que vous trouvez un préfixe (indiqué par un '.'), Continuez à partir du haut de l'arbre pour voir si vous pouvez trouver un suffixe à partir de ce point. Cela suppose que vous ne voulez rien entre le préfixe et le suffixe.