algorithm - 寻找所有回文子串的动态规划

Question

我试图通过动态规划解决一个问题。我有一个字符串，我需要找到所有可能的回文子串。比如说，我有一个长度为 n 的字符串。我为查找创建了一个矩阵 n*n。单元格 (i,j) 要么是 1，要么是 0。如果是 1，则表示子串 [i..j] 是回文，否则为 0。最初对角线为 1，因为每个字符本身就是一个回文。

我需要如上所述正确填充矩阵。

我想通了以下内容:

1. 如果 substring[i..j] 是一个原语，那么我可以通过检查矩阵是否在 O(1) 时间内找到 substring[i-1..j+1] 是否是回文[i][j]==1 and word[i-1] == word[j+1]..

对于其他一般情况，我该如何填充矩阵。

非常感谢使用伪代码/语言特定实现来填充矩阵的小解释

编辑:我需要一些关于矩阵填充的方式和顺序(即对角线、水平线等)的解释。我只想通过填写这个矩阵来解决这个问题，而不是通过其他方法。我的问题不是 this 的重复问题

Answer 1

可以检查长度为1到N的回文子串。

  For i from 1 to n
       Mark all substring of length i is palindromic or not.

伪代码:(基于字符串数组 1)

for len=1 to n:  // check string from length 1 to n
    for i=1 to (n-len + 1):  // substring start from 1 to （n-len+1)
        j = i + len - 1
        if len == 1:
           matrix[i][j]==1 
        else if len == 2:
           if array[i] == array[j]:
               matrix[i][j] = 1
           else:
               matrix[i][j] = 0
        else:
           if matrix[i+1][j-1] == 1 and array[i] == array[j]:
               matrix[i][j] = 1
           else:
               matrix[i][j] = 0