Prefixo comum mais longo de linhas

Question

Dado um arquivo de texto ou um fluxo de texto, como o prefixo comum mais longo de duas linhas pode ser determinado e impresso para stdout no bash? Se houver vários prefixos mais longos, não me importa qual deles é impresso.

Por exemplo, em uma entrada como:

abcdef
abc
defgh
abcdeg
defgi

O prefixo comum mais longo entre duas linhas é abcde (entre o primeiro e o quarto), o segundo mais longo defg , o terceiro abc ...

    

Answer 1

Você pode fazer algo como:

<file LC_ALL=C sort |
   sed -n 'N;h;s/^\(.*\).*\n.*//p;g;D' |
   awk '{l = length}
        l > max {max = l; s = $0}
        END {print s}'

Classificamos a entrada usando a comparação byte a byte ( sort no código do idioma C) que garante que as linhas com o maior prefixo comum sejam adjacentes.

sed encontra o prefixo comum mais longo entre uma linha e a próxima usando referências anteriores BRE ( \(.*\).*\n sendo uma sequência capturada de caracteres \(.*\) seguido por qualquer número de caracteres .* , uma nova linha \n e a mesma sequência de caracteres capturada anteriormente ), que imprimimos.

awk encontra o mais longo deles (escolhe o primeiro na entrada se houver vários, então será o primeiro na ordem lexical. Use >= em vez de > para obter o último).

Note que ele encontra o prefixo comum mais longo em termos de caracteres . Para tê-lo em termos de bytes , defina $LC_ALL para C para todos os 3 comandos, não apenas sort . Então, por exemplo, nas localidades UTF-8, em vez de encontrar o 2 caractere St como o prefixo comum mais longo entre Stéphane e Stábat , os 3 bytes, St<0xc3> onde <0xc3> serão encontrados a primeira metade dos caracteres á e é .

Para tê-lo em termos de cluster grapheme estendido . Por exemplo, para que entre Steps e Stéphane (onde é é expresso como o cluster de grafema de dois caracteres e\u0301 ) encontre St em vez de Ste , você pode recorrer a perl :

<file LC_ALL=C sort |
  perl -Mopen=locale -ne '
    BEGIN{$prev = <>}
    if ("$prev$_" =~ /^(\X*).*\n\b{g}/) {
      $l = length($1);
      if ($l > $max) {$max = $l; $s = $1}
    }
    $prev = $_;
    END{print "$s\n"}'

(onde \X corresponde a um cluster de grafema estendido e \b{g} an limite de cluster de grafema estendido (para o qual você precisa de perl 5.22.1 ou mais recente)).

Se você quisesse encontrar o prefixo comum mais longo de todas as linhas na entrada (não apenas quaisquer 2 linhas na entrada), como eu inicialmente pensei que você fosse perguntando, isso é respondido naquele outro Q & A aqui .