Lệnh shell để tìm chuỗi con dài nhất của hai chuỗi trong unix là gì?

Question

Lệnh shell để tìm chuỗi con dài nhất của hai chuỗi trong unix là gì? như: foo 'abcdefghi' 'abjklmdefnop' in: def

Answer 1

Điều này được gọi là vấn đề hậu quả phổ biến lâu nhất và có một số thuật toán tuyệt vời cho nó. Kiểm tra các giải pháp lập trình năng động (Nếu bạn google nó, bạn sẽ tìm thấy một tấn triển khai). Nếu bạn thực sự muốn hiểu điều này ở một mức độ thuật toán, kiểm tra MIT bài giảng này,

http://videolectures.net/mit6046jf05_leiserson_lec15/

Answer 2

Tôi không chắc chắn nếu có một lệnh duy nhất mà không được công việc cho bạn, nhưng kịch bản bash sau nên làm nó.

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

tiết kiệm ở trên như một tập tin substr.sh làm chmod + x substr.sh

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

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