Как искать слова, которые начинаются и заканчиваются другими словами из того же массива?

Question

У меня длинный список слов в массиве.Некоторые короткие, некоторые длинные.Я хотел бы отфильтровать те слова, которые начинаются со слова из массива (длина этого слова «префикс» может быть, скажем, 3 символа) и которые одновременно заканчиваются словом из него.

Скажем, первое слово - «навес для машины».Теперь, если в массиве тоже есть 'car' и 'port', я получу совпадение.Но если слово «carlsberg», я не получу совпадения (поскольку «lsberg», вероятно, не будет существующим словом в массиве).

Результаты предпочтительно будут отображаться как префиксное слово, суффиксслово, целое слово ".

Я бы подумал о том, чтобы использовать любой язык, который может заставить меня сделать это, хотя я сам в основном парень из JavaScript.

Answer 1

Интересно, поможет ли trie , см. Как наиболее часто используется структура данных "trie"? .

В Perl есть пара модулей для их сборки:

• Дерево :: 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 2

Я бы сделал что-то вроде:

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

Я написал это на месте, поэтому он может работать не совсем правильно.Но идея состоит в том, чтобы построить дерево префиксов и пройтись по нему.Каждый раз, когда вы найдете префикс (обозначенный знаком «.»), Продолжайте снова с вершины дерева, чтобы посмотреть, сможете ли вы найти суффикс с этой точки.Это предполагает, что вы ничего не хотите между префиксом и суффиксом.

Answer 3

Вот решение 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 4

Примерно так:

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

Ну, наивная реализация в 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;
}

Функция в ее текущей форме требует массив всех слов в качестве параметра и возвращает массив массивов, содержащих найденные тройки слов (первый элемент является префиксом, второй элемент является постфиксом, третий элемент является объединенным словом).