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.
For a second example, commonsubstring can find all common substrings of a given fixed length.
str1 = char('a' + round(rand(1,100)*1.5))
str2 = 'aaabbabbb';
substr,ind1,ind2] = commonsubstring(str1,str2,3)
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.
John D'Errico (2021). String subsequence tools (https://www.mathworks.com/matlabcentral/fileexchange/27460-string-subsequence-tools), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform CompatibilityWindows macOS Linux
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!