Python - दी गई स्ट्रिंग के सभी विशिष्ट पैलिंड्रोमिक सबस्ट्रिंग्स ढूंढना

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

तो, यदि इनपुट "bddaaa" जैसा है, तो आउटपुट [a, aa, aaa, b, d, dd] होगा।

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

• 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 := इंडेक्स 1 से अंत तक s
• 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 = {}
    n = len(s)
    matrix = [[0] * (n + 1) for _ 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