什么是shell命令查找unix中两个字符串的最长公共子字符串？
什么是shell命令查找unix中两个字符串的最长公共子字符串？ like：foo'abcdefghi''abjklmdefnop' prints：def什么是shell命令查找unix中两个字符串的最长公共子字符串？
这被称为最长的常见子序列问题，并且有一些很棒的算法。看看动态编程解决方案（如果你是谷歌，你会发现大量的实现）。如果你真的想在算法级理解这一点，看看这个麻省理工学院的演讲，
谢谢你这个不错的链接。但是现在恐怕我只需要一个快速的标准命令行解决方案，我不介意它是否以O（n^5）复杂度实现。 – user1081596 2012-02-22 11:26:18
@ user1081596：你的输入是多大？ – Daenyth 2012-02-23 16:53:12
我不知道是否有一个命令，没有工作适合你，但下面的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
这是否需要符合POSIX？针对任何特定的发行版？ – Daenyth 2012-02-21 20:29:29
最好在大多数linuxes上工作 – user1081596 2012-02-22 11:26:54
@ user1081596：然后我建议在perl中实现这个功能，因为它将安装在每个linux上，除非用户已经删除它。 – Daenyth 2012-02-23 16:36:00