algorithm - Fortran 中的 Morris Pratt 表

Question

我试过做 Morris Pratt 表，代码基本上是 C 中的这个:

void preMp(char *x, int m, int mpNext[]) {
int i, j;

i = 0;
j = mpNext[0] = -1;
while (i < m) {
   while (j > -1 && x[i] != x[j])
      j = mpNext[j];
   mpNext[++i] = ++j;
 }
}

这是我到目前为止在 Fortran 中的进展

program MP_ALGORITHM
implicit none
integer, parameter :: m=4
character(LEN=m) :: x='abac'
integer, dimension(4) :: T
integer :: i, j

i=0
T(1)=-1
j=-1

do while(i < m)
  do while((j > -1) .AND. (x(i+1:i+1) /= (x(j+i+1:j+i+1))))
    j=T(j)
  end do
  i=i+1
  j=j+1
  T(i)=j
end do
print *, T(1:)
end  program MP_ALGORITHM

问题是我认为我的输出有误。

对于 x=abac 应该是 (?):

a   b  a  c

-1  0  1  0

我的代码返回 0 1 1 1

那么，我做错了什么？

Answer 1

这里的问题是 C 索引从零开始，但 Fortran 索引从一开始。您可以尝试将每个数组访问的索引调整一个，但这会变得笨拙。

Morris-Pratt 表本身是一个索引数组，因此它在 C 和 Fortran 中看起来应该有所不同:Fortran 数组应该具有基于 1 的索引并且它应该使用零作为无效索引。

加上 chw21 指出的错误，您的函数可能如下所示:

subroutine kmp_table(x, t)
    implicit none

    character(*), intent(in) :: x
    integer, dimension(:), intent(out) :: t

    integer m
    integer :: i, j

    m = len(x)

    i = 1
    t(1) = 0
    j = 0

    do while (i < m)
        do while(j > 0 .and. x(i:i) /= x(j:j))
            j = t(j)
        end do
        i = i + 1
        j = j + 1
        t(i) = j
    end do
end subroutine 

然后您可以在 Morris-Pratt 算法中将其用作 taken straight from the Wikipedia page调整 Fortran 索引:

function kmp_index(S, W) result(res)
    implicit none

    integer :: res

    character(*), intent(in) :: S       ! text to search
    character(*), intent(in) :: W       ! word to find

    integer :: m                        ! zero-based offset in S
    integer :: i                        ! one-based offset in W and T

    integer, dimension(len(W)) :: T     ! KMP table



    call kmp_table(W, T)

    i = 1
    m = 0

    do while (m + i <= len(S))
        if (W(i:i) == S(m + i:m + i)) then
            if (i == len(W)) then
                res = m + 1
                return
            end if
            i = i + 1
        else
            if (T(i) > 0) then
                m = m + i - T(i)
                i = T(i)
            else
                i = 1
                m = m + 1
            end if
        end if
    end do

    res = 0

end function

(索引 m 在这里从零开始，因为 t 只在 S(m + i:m + i )。添加两个基于 1 的索引将产生偏移量 1，而保持 m 从零开始使其成为中性加法。m 是局部变量不会暴露给外部代码。)

或者，您可以通过为字符串和数组指定零的下限来使 Fortran 数组从零开始。不过，这将与有用的 character(*) 符号发生冲突，后者始终使用基于 one 的索引。在我看来，最好在典型的 Fortran 单基索引方案中考虑整个算法。