Python/dynamic_programming/longest_palindromic_substring.py at 6773a1fd9d4b188662042cf9686666582dcea046 · RamachandraBhardwaj/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# reference :https://www.geeksforgeeks.org/dsa/longest-palindromic-substring/


def longest_palindromic_substring(s: str) -> str:
    """
    This function returns longest palindromic substring in a string
    using Dynamic Programming.

    s : input string
    >>> longest_palindromic_substring("babad")
    'aba'
    >>> longest_palindromic_substring("cbbd")
    'bb'
    >>> longest_palindromic_substring("a")
    'a'
    >>> longest_palindromic_substring("ac")
    'a'
    >>> longest_palindromic_substring("")
    ''
    """
    n = len(s)

    dp = [[False for i in range(n)] for j in range(n)]
    start = 0
    max_length = 1

    for i in range(n):
        dp[i][i] = True
    # for length 2 palindrome check
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2

    # for length 3 and above
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_length = length

    return s[start : start + max_length]


def manacher_algorithm(s: str) -> str:
    """
    This function returns the longest palindromic substring in a string
    using Manacher's algorithm.

    s : input string
    t : transformed string
    p : array to store length of palindrome radius around each center
    c : center of the current rightmost palindrome
    r : right edge of the current rightmost palindrome
    n : length of transformed string

    >>> longest_palindromic_substring("babad")
    'aba'
    >>> longest_palindromic_substring("cbbd")
    'bb'
    >>> longest_palindromic_substring("a")
    'a'
    >>> longest_palindromic_substring("ac")
    'a'
    >>> longest_palindromic_substring("")
    ''
    """
    t = "^#" + "#".join(s) + "#$"
    n = len(t)

    p = [0] * n
    c = 0
    r = 0

    for i in range(1, n - 1):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        while t[i + (1 + p[i])] == t[i - (1 + p[i])]:
            p[i] += 1
        if i + p[i] > r:
            c = i
            r = i + p[i]

    max_length = max(p)
    max_center = p.index(max_length)
    start = (max_center - max_length) // 2
    return s[start : start + max_length]


if __name__ == "__main__":
    import doctest

    doctest.testmod()