在Unix中，查找两个字符串的最长公共子串的shell命令是什么？

Question

在Unix系统中，查找两个字符串的最长公共子串的shell命令是什么？ 例如：foo 'abcdefghi' 'abjklmdefnop' 输出结果为：def

- user1081596

---

这需要符合POSIX标准吗？针对特定的发行版吗？ - Daenyth

最好让它在大多数Linux上都能正常工作。 - user1081596

@user1081596：那我建议用Perl来实现，因为它会被安装在每个Linux上，除非用户已经将其删除。 - Daenyth

在这种情况下，为什么Perl比Ruby、Python或其他任何脚本语言更好呢？ - Anderson Green

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 然后执行chmod +x substr.sh

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

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

- pranithk

Answer 2

这被称为最长公共子序列问题，有一些很棒的算法可以解决它。查看动态规划解决方案（如果你谷歌一下，会找到大量实现）。如果你真的想在算法层面上理解这个问题，请查看这个麻省理工学院的讲座。

http://videolectures.net/mit6046jf05_leiserson_lec15/

- Avi

---

谢谢您提供这个不错的链接。但是目前我只需要一个快速的标准命令行解决方案，如果它的复杂度是O(n^5)，我也不介意。 - user1081596

@user1081596：你的输入大小会是多少？ - Daenyth