पायथन में स्ट्रिंग में पालिंड्रोमिक बॉर्डर्स का पता लगाने का प्रोग्राम

मान लीजिए हमें एक स्ट्रिंग str दी गई है। एक स्ट्रिंग का बॉर्डर एक सबस्ट्रिंग है जो उस स्ट्रिंग का उचित प्रीफिक्स और सफिक्स है। उदाहरण के लिए, 'ab' स्ट्रिंग 'ababab' का एक बॉर्डर है। एक बॉर्डर को पालिंड्रोम बॉर्डर कहा जाता है यदि बॉर्डर स्ट्रिंग एक पालिंड्रोम है। अब मान लीजिए f(str) दी गई स्ट्रिंग str में पालिंड्रोम बॉर्डर्स की संख्या है। हमें str के सभी गैर-खाली सबस्ट्रिंग्स str_k के लिए f(str_k) का योग ढूंढना है। योग बड़ा हो सकता है, इसलिए 10^9 + 7 द्वारा मॉड्यूलो ऑपरेशन किया जा सकता है।

उदाहरण के लिए, यदि इनपुट str = 'pqpqp' है, तो आउटपुट 5 होगा। स्ट्रिंग 'pqpqp' के 15 सबस्ट्रिंग्स मौजूद हैं; हालांकि केवल 4 सबस्ट्रिंग्स में पालिंड्रोमिक बॉर्डर्स हैं। स्ट्रिंग्स हैं:

pqp : f(pqp) = 1
pqpqp : f(pqpqp) = 2
qpq : f(qpq) = 1
pqp : f(pqp) = 1
इन मानों का योग 1 + 2 + 1 + 1 = 5 है।

समाधान दृष्टिकोण

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

palindrome_calculator() नामक एक फंक्शन परिभाषित करें। यह input_dict लेगा
- ans := 0
- input_dict के मानों में प्रत्येक item1, item2 के लिए, करें
  - ans := ans + item2 * (item2 - 1 का फ्लोर मान / 2)
- ans लौटाएं
str_check() नामक एक फंक्शन परिभाषित करें। यह स्ट्रिंग लेगा
- t_str := string[0]
- string में प्रत्येक s के लिए, करें
  - यदि s, t_str के समान नहीं है, तो
    - False लौटाएं
  - True लौटाएं
string_res() नामक एक फंक्शन परिभाषित करें। यह स्ट्रिंग लेगा
- ans := 0
- i के लिए 2 से स्ट्रिंग के आकार + 1 तक की रेंज में, करें
  - ans := ans + i * (i - 1 का फ्लोर मान / 2)
  - ans := ans mod 1000000007
- ans लौटाएं
यदि str_check(string) True है, तो
- string_res(string) लौटाएं
ans := 0
odd_list := एक नई सूची जिसमें एक नई सूची, एक नया मैप, और 1 हो
string में प्रत्येक s के लिए, करें
- यदि s, odd_list[1] में मौजूद नहीं है, तो
  - odd_list[1, s] := 0
- odd_list[1, s] := odd_list[1, s] + 1
i के लिए 0 से स्ट्रिंग के आकार तक की रेंज में, करें
- i को odd_list[0] के अंत में डालें
ans := ans + palindrome_calculator(odd_list[1])
even_list := एक नई सूची जिसमें एक नई सूची, एक नया मैप, और 1 हो
i के लिए 0 से स्ट्रिंग के आकार - 1 तक की रेंज में, करें
- यदि string[i], string[i + 1] के समान है, तो
  - i को even_list[0] के अंत में डालें
  - tmp := string[इंडेक्स i से i + 2 तक]
  - यदि tmp, even_list[1] में मौजूद नहीं है, तो
    - even_list[1, tmp] := 0
  - even_list[1, tmp] := even_list[1, tmp] + 1
ans := ans + palindrome_calculator(even_list[1])
val के लिए 3 से स्ट्रिंग के आकार तक की रेंज में, करें
- यदि val mod 2, 0 के समान है, तो
  - wt := even_list
- अन्यथा,
  - wt := odd_list
- new_t := एक नई सूची जिसमें एक नई सूची, एक नया मैप, और val हो
- wt[0] में प्रत्येक index के लिए, करें
  - यदि index - 1 >= 0 और index + val - 2 < स्ट्रिंग का आकार और string[index - 1], string[index + val - 2] के समान है, तो
    - index - 1 को new_t[0] के अंत में डालें
    - tmp := string[इंडेक्स index - 1 से index - 1 + val तक]
    - यदि tmp, new_t[1] में मौजूद नहीं है, तो
      - new_t[1, tmp] := 0
    - new_t[1, tmp] := new_t[1, tmp] + 1
- ans := ans + palindrome_calculator(new_t[1])
- ans := ans mod 1000000007
- यदि val mod 2, 0 के समान है, तो
  - even_list := new_t
- अन्यथा,
  - odd_list := new_t
ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def palindrome_calculator(input_dict):
    ans = 0
    for item1, item2 in input_dict.items():
        ans += item2 * (item2 - 1) // 2
    return ans

def str_check(string):
    t_str = string[0]
    for s in string:
        if s != t_str:
            return False
    return True

def string_res(string):
    ans = 0
    for i in range(2, len(string) + 1):
        ans += i * (i - 1) // 2
        ans %= 1000000007
    return ans

def solve(string):
    if str_check(string):
        return string_res(string)
    ans = 0
    odd_list = [[], {}, 1]
    for s in string:
        if s not in odd_list[1]:
            odd_list[1][s] = 0
        odd_list[1][s] += 1
    for i in range(len(string)):
        odd_list[0].append(i)
    ans += palindrome_calculator(odd_list[1])
    even_list = [[], {}, 1]
    for i in range(len(string) - 1):
        if string[i] == string[i + 1]:
            even_list[0].append(i)
            tmp = string[i:i + 2]
            if tmp not in even_list[1]:
                even_list[1][tmp] = 0
            even_list[1][tmp] += 1
    ans += palindrome_calculator(even_list[1])
    for val in range(3, len(string)):
        if val % 2 == 0:
            wt = even_list
        else:
            wt = odd_list
        new_t = [[], {}, val]
        for index in wt[0]:
            if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
                new_t[0].append(index - 1)
                tmp = string[index - 1 : index - 1 + val]
                if tmp not in new_t[1]:
                    new_t[1][tmp] = 0
                new_t[1][tmp] += 1
        ans += palindrome_calculator(new_t[1])
        ans %= 1000000007
        if val % 2 == 0:
            even_list = new_t
        else:
            odd_list = new_t
    return ans

print(solve('pqpqp'))

इनपुट

'pqpqp'