Che cos'è un comando di shell per trovare la sottostringa comune più lunga di due stringhe in unix? come: foo 'abcdefghi' 'abjklmdefnop' stampe: defChe cos'è un comando shell per trovare la sottostringa comune più lunga di due stringhe in unix?
Questo è noto come la massima sottosequenza comune e ci sono alcuni grandi algoritmi per esso. Dai un'occhiata alla soluzione di programmazione dinamica (se cerchi su google, troverai un sacco di implementazioni). Se davvero si vuole capire questo a un livello algoritmico, controlla questa conferenza MIT,
Grazie per questo link. Ma per ora temo di avere solo bisogno di una soluzione standard a linea di comando rapida e non mi dispiacerebbe se fosse implementato con la complessità di O (n^5). – user1081596
@ user1081596: Che dimensioni saranno i tuoi input? – Daenyth
io non sono sicuro se c'è un unico comando che fa il lavoro per voi, ma il seguente script bash dovrebbe fare esso.
#!/bin/bash
word1="$1"
word2="$2"
if [ ${#word1} -lt ${#word2} ]
then
word1="$2"
word2="$1"
fi
for ((i=${#word2}; i>0; i--)); do
for ((j=0; j<=${#word2}-i; j++)); do
if [[ $word1 =~ ${word2:j:i} ]]
then
echo ${word2:j:i}
exit
fi
done
done
Salva quanto sopra come un file substr.sh fare chmod + x substr.sh
pranithk @ ~
09:24:32 :) $ ./substr.sh 'abcdefghi' 'abcdeghi'
abcde
pranithk @ ~
09:24:33 :) $ ./substr.sh 'abcdefghi' 'abjklmdefnop'
def
Questo bisogno di essere POSIX? Mirato a qualsiasi specifica distribuzione? – Daenyth
è meglio farlo funzionare sulla maggior parte degli linux – user1081596
@ user1081596: Quindi consiglio di implementarlo in perl, perché verrà installato su ogni linux a meno che l'utente non lo abbia rimosso. – Daenyth