পাইথনে দেওয়া স্ট্রিংয়ের সব স্বতন্ত্র প্যালিনড্রোমিক সাব-স্ট্রিং খুঁজে বের করা

मान लीजिए हमारे पास लोअरकेस ASCII कॅरेक्टर्स वाली एक स्ट्रिंग है। हमें इसके सभी विशिष्ट सन्निकट पैलिंड्रोमिक सबस्ट्रिंग ढूंढने हैं।

उदाहरण के लिए, यदि इनपुट "bddaaa" है, तो आउटपुट होगा [a, aa, aaa, b, d, dd]

समाधान दृष्टिकोण (Manacher's Algorithm)

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

m := एक नया मैप
n := s का आकार
matrix := n संख्या के 0 की दो पंक्तियां बनाएं
s := "@" + s + "#"
j के लिए 0 से 1 तक की रेंज में:
- temp := 0
- matrix[j, 0] := 0
- i := 1
- जब तक i <= n:
  - जब तक s[i - temp - 1] == s[i + j + temp]: temp := temp + 1
  - matrix[j, i] := temp
  - k := 1
  - जब तक (matrix[j, i - k] != temp - k) और k < temp:
    - matrix[j,i+k] := min(matrix[j, i-k], temp - k)
    - k := k + 1
  - temp := max(temp - k, 0)
  - i := i + k
s := s[1:len(s)-1]
m[s[0]] := 1
i के लिए 1 से n तक की रेंज में:
- j के लिए 0 से 1 तक की रेंज में:
  - temp के लिए matrix[j][i] से 0 तक घटते क्रम में:
    - m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
- m[s[i]] := 1
m में प्रत्येक i के लिए, i प्रदर्शित करें

उदाहरण कोड

def find_substr(s):
    m = dict()
    n = len(s)
    matrix = [[0 for x in range(n+1)] for x in range(2)]
    s = "@" + s + "#"
    for j in range(2):
        temp = 0
        matrix[j][0] = 0
        i = 1
        while i <= n:
            while s[i - temp - 1] == s[i + j + temp]:
                temp += 1
            matrix[j][i] = temp
            k = 1
            while (matrix[j][i - k] != temp - k) and (k < temp):
                matrix[j][i+k] = min(matrix[j][i-k], temp - k)
                k += 1
            temp = max(temp - k, 0)
            i += k
    s = s[1:len(s)-1]
    m[s[0]] = 1
    for i in range(1,n):
        for j in range(2):
            for temp in range(matrix[j][i],0,-1):
                m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
        m[s[i]] = 1
    for i in m:
        print(i)

find_substr("bddaaa")

इनपुट

bddaaa

आउटपुट

a aa b aaa d dd