longest_common_substring Function

public function longest_common_substring(a, b) result(match)

NAME

longest_common_substring(3f) - [M_strings:COMPARE] function that
returns the longest common substring of two strings.

SYNOPSIS

function longest_common_substring(a,b) result(match)

 character(len=*),intent(in)  :: a, b
 character(len=:),allocatable :: match

DESCRIPTION

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".

OPTIONS

a,b  strings to search for the longest common substring.

RETURNS

longest_common_substring  the longest common substring found

EXAMPLE

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"

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(in) :: a
character(len=*), intent(in) :: b

Return Value character(len=:), allocatable


Contents

Source Code

longest_common_substring

Source Code

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