Fortran 语言的莫里斯普拉特 table

Question

我试过做 Morris Pratt table，代码基本上是 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

这个站点并不是真正的调试站点。通常我会建议你看看如何调试代码。我没花很长时间就用笔和纸检查了您的代码并验证那确实是它产生的 table。

不过，这里有一些提示：

C代码比较x[i]和x[j]，但是你在Fortran代码中比较x[i]和x[i+j]，或多或少。
在 Fortran 中，整数数组通常也从索引 1 开始。所以就像在x字符串中的索引加一一样，每次在任何地方访问T也需要加1。

Answer 2

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

Morris-Pratt table 本身是一个索引数组，因此它在 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) 中与 i 一起使用。添加两个从一开始的索引将产生一个偏移量一个，而保持 m 从零开始使它成为一个中立的添加。m 是一个局部变量，不会暴露给外部代码。）

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

Fortran 语言的莫里斯普拉特 table

Morris Pratt table in Fortran

algorithm

fortran

string-search