String subsequence tools

Identify common substrings of a pair of strings

Zhiping XU's submission on the FEX intrigued me. I knew it had to be doable more efficiently. Long strings will be common, so it makes much sense to have an efficient code. You might find these tools interesting for inspecting strings of DNA bases, or for checking a student's homework submission for plagiarized content. Surely there are other uses too.

The commonsubstring.m function does this search fairly efficiently (though I am sure it too can be enhanced.)

Generate a pair of long random letter sequences, then determine the longest common substring between them. In the following example, the original strings each had 10^5 random elements in them.

bases = 'acgt';
str1 = bases(ceil(rand(1,100000)*4));
str2 = bases(ceil(rand(1,100000)*4));

tic,[substr,ind1,ind2] = commonsubstring(str1,str2);toc
Elapsed time is 16.650532 seconds.

There were two substrings found of the maximum length (16) characters. These substrings started at locations 22189 and 74425 in str1, and at locations 64948 and 32833 in str2.

substr =
gctttagggcgtacgc
cttcggataccttgtt

ind1 =
[22189]
[74425]

ind2 =
[64948]
[32833]

For a second example, commonsubstring can find all common substrings of a given fixed length.

str1 = char('a' + round(rand(1,100)*1.5))
str1 =
bbbabbbbbabbbbbbabbbbbabbababbbabbabbbbbbabbbbbbbbbbbbbabbaaabbbbbaabbbbbbbbbbabbbbbaaabbabbaabbbbbb

str2 = 'aaabbabbb';

substr,ind1,ind2] = commonsubstring(str1,str2,3)
substr =
aaa
aab
abb
bab
bba
bbb

ind1 =
[1x2 double]
[1x4 double]
[1x15 double]
[1x11 double]
[1x15 double]
[1x19 double]

ind2 =
[ 1]
[ 2]
[1x2 double]
[ 5]
[ 4]
[ 7]

In addition, I've also included the function substrings.m. It returns a list of all substrings of a given string. In the example below, it returns all distinct substrings of length 3 from str1 above.

substrings(str1,3,1)
ans =
aaa
aab
aba
abb
baa
bab
bba
bbb