longest_common_substring(3f) - [M_strings:COMPARE] function that
returns the longest common substring of two strings.
function longest_common_substring(a,b) result(match)
character(len=*),intent(in) :: a, b
character(len=:),allocatable :: match
function that returns the longest common substring of two strings.
Note that substrings are consecutive characters within a string.
This distinguishes them from subsequences, which is any sequence of
characters within a string, even if there are extraneous characters in
between them.
Hence, the longest common subsequence between "thisisatest" and
"testing123testing" is "tsitest", whereas the longest common substring
is just "test".
a,b strings to search for the longest common substring.
longest_common_substring the longest common substring found
Sample program
program demo_longest_common_substring
use M_strings, only : longest_common_substring
implicit none
call compare('testing123testingthing','thisis', 'thi')
call compare('testing', 'sting', 'sting')
call compare('thisisatest_stinger','testing123testingthing','sting')
call compare('thisisatest_stinger', 'thisis', 'thisis')
call compare('thisisatest', 'testing123testing', 'test')
call compare('thisisatest', 'thisisatest', 'thisisatest')
contains
subroutine compare(a,b,answer)
character(len=*),intent(in) :: a, b, answer
character(len=:),allocatable :: match
character(len=*),parameter :: g='(*(g0))'
match=longest_common_substring(a,b)
write(*,g) 'comparing "',a,'" and "',b,'"'
write(*,g) merge('(PASSED) "','(FAILED) "',answer == match), &
& match,'"; expected "',answer,'"'
end subroutine compare
end program demo_longest_common_substring
expected output
comparing "testing123testingthing" and "thisis"
(PASSED) "thi"; expected "thi"
comparing "testing" and "sting"
(PASSED) "sting"; expected "sting"
comparing "thisisatest_stinger" and "testing123testingthing"
(PASSED) "sting"; expected "sting"
comparing "thisisatest_stinger" and "thisis"
(PASSED) "thisis"; expected "thisis"
comparing "thisisatest" and "testing123testing"
(PASSED) "test"; expected "test"
comparing "thisisatest" and "thisisatest"
(PASSED) "thisisatest"; expected "thisisatest"
Type | Intent | Optional | Attributes | Name | ||
---|---|---|---|---|---|---|
character(len=*), | intent(in) | :: | a | |||
character(len=*), | intent(in) | :: | b |
function longest_common_substring(a,b) result(match)
character(len=*),intent(in) :: a, b
character(len=:),allocatable :: match
character(len=:),allocatable :: a2, b2
integer :: left, foundat, len_a, i
if(len(a) < len(b))then ! to reduce required comparisions look for shortest string in longest string
a2=a
b2=b
else
a2=b
b2=a
endif
match=''
do i=1,len(a2)-1
len_a=len(a2)
do left=1,len_a
foundat=index(b2,a2(left:))
if(foundat /= 0.and.len(match) < len_a-left+1)then
if(len(a2(left:)) > len(match))then
match=a2(left:)
exit
endif
endif
enddo
if(len(a2) < len(match))exit
a2=a2(:len(a2)-1)
enddo
end function longest_common_substring