पायथन में दो तारों से उपसर्ग संपीड़न करने का कार्यक्रम

मान लीजिए कि हमारे पास दो स्ट्रिंग्स s और t हैं (दोनों में लोअरकेस अंग्रेजी अक्षर हैं)। हमें आकार 3 के जोड़े की एक सूची ढूंढनी है, जहां प्रत्येक जोड़ी इस रूप में है (l, k) यहां k एक स्ट्रिंग है और l इसकी लंबाई है। अब इन तीन युग्मों में, पहले एक में s और t का सबस्ट्रिंग शामिल है जो इन दो स्ट्रिंग्स का सबसे लंबा सामान्य उपसर्ग p है, फिर s का शेष भाग s' है और t का शेष भाग t है। तो अंतिम सूची इस तरह होगी [(पी की लंबाई, पी), (एस की लंबाई, एस'), (टी की लंबाई, टी')]।

इसलिए, यदि इनपुट s ="विज्ञान" t ="स्कूल" जैसा है, तो आउटपुट [(2, 'sc'), (5, 'ience'), (4, 'hool')]

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

• एलसीपी:=खाली स्ट्रिंग
• मैं के लिए 0 से न्यूनतम आकार के आकार या टी के आकार में, करते हैं
  • यदि s[i] t[i] के समान है, तो
    • एलसीपी:=एलसीपी + एस[i]
• s_rem :=इंडेक्स से अंत तक s का सबस्ट्रिंग (lcp का आकार)
• t_rem :=इंडेक्स से अंत तक t का सबस्ट्रिंग (lcp का आकार)
• तीन जोड़े की सूची लौटाएं [(lcp का आकार, lcp) ,(s_rem का आकार, s_rem) ,(t_rem का आकार, t_rem)]

उदाहरण

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

def solve(s, t):
   lcp = ''
   for i in range(min(len(s), len(t))):
      if s[i] == t[i]:
         lcp += s[i]

   s_rem = s[len(lcp):]
   t_rem = t[len(lcp):]
   return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)]

s = "science"
t = "school"
print(solve(s, t))

इनपुट

"science", "school"

आउटपुट

[(2, 'sc'), (5, 'ience'), (4, 'hool')]