Как работает эта функция для нахождения палиндромов?

Question

[Алексей Белов]

Всем привет, мне нужно понять как работает эта функция, а именно такие моменты, с cps мы получаем матрицу, но зачем ее расширять на 2, как это будет использоватся дальше, мб кто то знает этот алгоритм, скиньте ссылку.

def pal(str): 
    N = len(str) 
    cps = [[0 for i in range(N + 2)]for j in range(N + 2)] 
    
    for i in range(N): 
        cps[i][i] = 1

    for L in range(2, N + 1):
        for i in range(N): 
            k = L + i - 1
            if (k < N): 
                if (str[i] == str[k]): 
                    cps[i][k] = (cps[i][k - 1] +
                    cps[i + 1][k] + 1) 
                else: 
                    cps[i][k] = (cps[i][k - 1] +
                    cps[i + 1][k] -
                    cps[i + 1][k - 1]) 

    return cps[0][N - 1]

Answer 1

[bogolt]

Рекомендую вам выводить матрицы после каждого прохода цикла, думаю, что это наведет на понимание его работы.