What is a shell command to find the longest common substring of two strings in unix?

Question

What is a shell command to find the longest common substring of two strings in unix? like: foo 'abcdefghi' 'abjklmdefnop' prints: def

Does this need to be POSIX? Targeted at any specific distro? — Daenyth
– Daenyth, Commented Feb 21, 2012 at 20:29
@user1081596: Then I recommend implementing this in perl, because it will be installed on every linux unless the user has removed it. — Daenyth
– Daenyth, Commented Feb 23, 2012 at 16:36
@user1081596 In this case, why would Perl be a better choice than Ruby, Python, or any other scripting language? — Anderson Green
– Anderson Green, Commented Jan 8, 2013 at 20:35

pranithk · Accepted Answer · 2012-02-23 04:00:11Z

4

I am not sure if there is a single command that does the job for you but the following bash script should do it.

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

save the above as a file 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

answered Feb 23, 2012 at 4:00

pranithk

5593 silver badges2 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Avi · Accepted Answer · 2012-02-21 18:39:09Z

2

This is known as the longest common subsequence problem and there are some great algorithms for it. Check out the dynamic programming solution (If you google it, you'll find a ton of implementations). If you really want to understand this at an algorithmic level, check out this MIT lecture,

http://videolectures.net/mit6046jf05_leiserson_lec15/

answered Feb 21, 2012 at 18:39

Avi

1,35610 silver badges27 bronze badges

2 Comments

user1081596 Over a year ago

Thank you for this nice link. But for now I am afraid I just need a quick standard command line solution and I would not mind if it is implemented with O(n^5) complexity.

Daenyth Over a year ago

@user1081596: What size will your inputs be?

Collectives™ on Stack Overflow

What is a shell command to find the longest common substring of two strings in unix?

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related