1- MAX_LEN = 1000
1+ """
2+ This is a Python implementation for checking whether a substring is palindromic or not.
23
3- text = ""
4- dp = [[False for i in range (MAX_LEN )]for i in range (MAX_LEN )]
4+ For testing run:
5+ python3 is_substring_palindrome.py
6+ """
57
6- def preprocess (s ):
8+ def preprocess_all_substrings (text ):
9+ """Find all palindromic substrings of a string, using dynamic programming, with O(n^2) time complexity.
10+
11+ Args:
12+ text: the string to be preprocessed.
13+ Returns:
14+ A 2-dimentional matrix called ret.
15+ ret[i][j] is True, if and only if the substring text[i:j+1] is palindromic.
716 """
8- Preprocesses a string using dynamic programming.
9- Time complexity: O(n^2)
10- """
11- global text
12- global dp
13- text = s
14- n = len (s )
15- dp = [[False for i in range (n )]for i in range (n )]
17+ n = len (text )
18+ ret = [[False for i in range (n )]for j in range (n )]
1619
1720for i in range (n ):
18- dp [i ][i ]= True
19-
20- for i in range (n - 1 ):
21- dp [i ][i + 1 ]= (text [i ]== text [i + 1 ])
21+ ret [i ][i ]= True
22+ if i + 1 < n :
23+ ret [i ][i + 1 ]= (text [i ]== text [i + 1 ])
2224
2325for substr_len in range (2 ,n + 1 ):
2426for i in range (n - substr_len + 1 ):
2527j = i + substr_len - 1
26- dp [i ][j ]= (text [i ]== text [j ]and dp [i + 1 ][j - 1 ])
28+ ret [i ][j ]= (text [i ]== text [j ]and ret [i + 1 ][j - 1 ])
2729
30+ return ret
2831
29- def is_substring_palindrome (l ,r ):
30- """
31- Returns True if and only if the substring text[l:r] is a palindrome.
32- Time complexity: O(1)
33- Call preprocess function at least once, before calling this function.
32+
33+ def is_substring_palindrome (dp ,l ,r ):
34+ """Check whether a substring is palindromic or not, with O(1) time complexity.
35+
36+ Args:
37+ dp: a preprocessed 2-dimentional matrix.
38+ dp[i][j] has been set to True, if and only if the substring text[i:j+1] is palindromic.
39+ l: left most character of the substring index
40+ r: right most character of the substring index
41+ Returns:
42+ True, if and only if text[l:r+1] substring is palindromic.
43+ False, if and only if text[l:r+1] substring is not palindromic.
3444 """
35- n = len (text )
45+ n = len (dp )
3646if l >= r or l < 0 or r > n :
3747return False
3848else :
@@ -42,20 +52,20 @@ def is_substring_palindrome(l, r):
4252if __name__ == '__main__' :
4353s = "'nursesrun' and 'racecar' are some palindromes."
4454
45- preprocess (s )
55+ dp = preprocess_all_substrings (s )
4656
4757# Answering some queries:
48- if is_substring_palindrome (1 ,10 ):
58+ if is_substring_palindrome (dp , 1 ,10 ):
4959print (s [1 :10 ],"is a palindrome." )
5060else :
5161print (s [1 :10 ],"is not a palindrome." )
5262
53- if is_substring_palindrome (17 ,24 ):
63+ if is_substring_palindrome (dp , 17 ,24 ):
5464print (s [17 :24 ],"is a palindrome." )
5565else :
5666print (s [17 :24 ],"is not a palindrome." )
5767
58- if is_substring_palindrome (35 ,45 ):
68+ if is_substring_palindrome (dp , 35 ,45 ):
5969print (s [35 :45 ],"is a palindrome." )
6070else :
6171print (s [35 :45 ],"is not a palindrome." )