Что такое команда оболочки, чтобы найти самую длинную общую подстроку из двух строк в Unix?

Question

Что такое команда оболочки для поиска самой длинной общей подстроки из двух строк в unix? как: foo 'abcdefghi' 'abjklmdefnop' печать: def

Answer 1

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

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

сохранить вышеперечисленное как файл substr.sh do chmod + x substr.sh

pranithk @ ~
09:24:32 :) $ ./substr.sh 'abcdefghi' 'abcdeghi'
abcde

pranithk @ ~
09:24:33 :) $ ./substr.sh 'abcdefghi' 'abjklmdefnop'
def

Answer 2

Это известно как самая длинная общая проблема подпоследовательности, и есть несколько хороших алгоритмов для нее.Посмотрите решение для динамического программирования (если вы его найдете в Google, вы найдете массу реализаций).Если вы действительно хотите понять это на алгоритмическом уровне, прочитайте эту лекцию MIT,

http://videolectures.net/mit6046jf05_leiserson_lec15/