पायथन में एक स्ट्रिंग और उसके सबस्ट्रिंग्स की कुल समानता खोजने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है। हमें स्ट्रिंग s की उसके प्रत्येक सफ़िक्स के साथ समानता का योग ढूंढना है। यहां दो स्ट्रिंग्स के बीच समानता दोनों स्ट्रिंग्स के सबसे लंबे कॉमन प्रीफिक्स की लंबाई है।

उदाहरण के लिए, यदि इनपुट s = "pqpqpp" है, तो आउटपुट 11 होगा क्योंकि स्ट्रिंग के सफ़िक्स हैं "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" और "p"। इन सबस्ट्रिंग्स की स्ट्रिंग "pqpqpp" के साथ समानताएं क्रमशः 6, 0, 3, 0, 1, और 1 हैं। तो योग 6 + 0 + 3 + 0 + 1 + 1 = 11 है।

हल करने के चरण

1. length := len(s)
2. total := length
3. z := [0] से शुरू होने वाली सूची
4. l := 0, r := 0
5. k को 1 से length - 1 तक लूप चलाएं:
   • यदि k > r, तो:
     • match := 0
     • index := k
   • index < length तक व्हाइल लूप चलाएं:
     • यदि s[index] == s[match], तो match += 1, index += 1
     • अन्यथा, लूप से बाहर निकलें।
   • match को z के अंत में जोड़ें।
   • यदि match > 0, तो:
     • total := total + match
     • l := k
     • r := index - 1
   • अन्यथा:
     • यदि z[k-l] < (r-k)+1, तो:
       • z[k-l] को z के अंत में जोड़ें
       • total := total + z[k-l]
     • अन्यथा:
       • match := r - k
       • index := r
       • index < length तक व्हाइल लूप चलाएं:
         • यदि s[index] == s[match], तो match += 1, index += 1
         • अन्यथा, लूप से बाहर निकलें।
       • match को z के अंत में जोड़ें
       • total := total + match
       • l := k
       • r := index - 1
6. total वापस करें।

उदाहरण

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

def solve(s):
    length = len(s)
    total = length
    z = [0]
    l = 0
    r = 0
    for k in range(1, length):
        if k > r:
            match = 0
            index = k
            while index < length:
                if s[index] == s[match]:
                    match += 1
                    index += 1
                else:
                    break
            z.append(match)
            if match > 0:
                total += match
                l = k
                r = index - 1
            else:
                if z[k-l] < (r-k)+1:
                    z.append(z[k-l])
                    total += z[k-l]
                else:
                    match = r - k
                    index = r
                    while index < length:
                        if s[index] == s[match]:
                            match += 1
                            index += 1
                        else:
                            break
                    z.append(match)
                    total += match
                    l = k
                    r = index - 1
    return total

s = "pqpqpp"
print(solve(s))

इनपुट

"pqpqpp"

आउटपुट

11