पायथन में दो स्ट्रिंग्स से प्रीफिक्स कम्प्रेशन करने का प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट s = "science" t = "school" है, तो आउटपुट [(2, 'sc'), (5, 'ience'), (4, 'hool')] होगा।

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

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

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