पायथन में स्ट्रिंग और उसके सफ़िक्स के बीच समानता की गणना करना

मान लीजिए हमें एक स्ट्रिंग 'input_str' दी गई है। यदि हम input_str से सभी सफ़िक्स निर्धारित करते हैं; उदाहरण के लिए यदि स्ट्रिंग 'abcd' है, तो सफ़िक्स हैं 'abc', 'bcd', 'cd', 'd'। अब, हम input_str और सभी सफ़िक्स के बीच समानता की जांच करते हैं, जो input_str और एक सफ़िक्स में सबसे लंबे कॉमन प्रीफिक्स की लंबाई से मापी जाती है। input_str और सभी सफ़िक्स के बीच समानताओं का योग लौटाना है।

उदाहरण के लिए, यदि इनपुट है input_str = 'tpotp', तो आउटपुट होगा 7।

स्ट्रिंग 'tpotp' के सभी सफ़िक्स हैं: 'tpotp', 'potp', 'otp', 'tp', और 'p'।

यदि हम सभी सफ़िक्स की input_str के साथ समानता जांचते हैं, तो हमें मिलता है:

'tpotp' समानता 5
'potp' समानता 0
'otp' समानता 0
'tp' समानता 2
'p' समानता 0
समानताओं का योग = 5 + 0 + 0 + 2 + 0 = 7।

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

यह समस्या Z-एल्गोरिथ्म का एक क्लासिक अनुप्रयोग है। Z-एल्गोरिथ्म रैखिक समय में एक स्ट्रिंग के प्रत्येक पोजीशन के लिए सबसे लंबे कॉमन प्रीफिक्स की लंबाई की गणना करता है।

return_list को स्ट्रिंग की लंबाई से आरंभ करें (पहला सफ़िक्स पूरी स्ट्रिंग है)।
विंडो वेरिएबल्स p, q, r का उपयोग करके पहले से गणना किए गए Z-मानों का लाभ उठाएं।
प्रत्येक पोजीशन i के लिए, यदि यह वर्तमान Z-बॉक्स के भीतर है, तो पहले से गणना किए गए मानों का उपयोग करें; अन्यथा, स्पष्ट तुलना करें।
सभी Z-मानों का योग लौटाएं।

पायथन कार्यान्वयन

def solve(input_str):
    return_list = [len(input_str)]
    i = 1
    p, q = 0, 0
    r = 0
    while i < len(input_str):
        if q < i < (q + p):
            if return_list[i - q] >= q + p - i:
                r = q + p - i
                p, q = 0, 0
            else:
                return_list.append(return_list[i - q])
                i += 1
                r = 0
        else:
            while i + r < len(input_str) and input_str[r] == input_str[i + r]:
                r += 1
            return_list.append(r)
            p, q = r, i
            i += 1
            r = 0
    return sum(return_list)

print(solve('tpotp'))

इनपुट

'tpotp'