¿Qué es un comando de shell para encontrar la subcadena común más larga de dos cadenas en Unix? como: Foo abcdefghi ' 'abjklmdefnop' impresiones: def¿Qué es un comando de shell para encontrar la subcadena común más larga de dos cadenas en Unix?
Esto se conoce como el problema subsecuencia común más larga y hay algunos grandes algoritmos para ello. Consulte la solución de programación dinámica (si la busca en Google, encontrará muchas implementaciones). Si realmente quiere entender esto en un nivel algorítmico, echa un vistazo a esta conferencia del MIT,
Gracias por este bonito enlace. Pero por ahora me temo que solo necesito una solución de línea de comandos estándar rápida y no me importaría si se implementa con O (n^5) complejidad. – user1081596
@ user1081596: ¿De qué tamaño serán sus entradas? – Daenyth
no estoy seguro de si hay un solo comando que hace el trabajo para usted, pero la siguiente escritura del golpe debe hacer eso.
#!/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
Guardar todo lo anterior como un archivo substr.sh hacer chmod + x substr.sh
pranithk @ ~
09:24:32 :) $ ./substr.sh 'abcdefghi' 'abcdeghi'
abcde
pranithk @ ~
09:24:33 :) $ ./substr.sh 'abcdefghi' 'abjklmdefnop'
def
¿Esta necesidad de ser POSIX? ¿Dirigido a cualquier distribución específica? – Daenyth
es mejor tenerlo funcionando en la mayoría de los linux – user1081596
@ user1081596: Entonces recomiendo implementar esto en Perl, ya que se instalará en cada Linux a menos que el usuario lo haya eliminado. – Daenyth