पायथन में सबस्ट्रिंग्स के इंडेक्स ढूंढना जो किसी अन्य स्ट्रिंग से पूरी तरह मेल खाते हों या एक पोजीशन पर अलग हों

मान लीजिए हमें दो स्ट्रिंग्स दी गई हैं। पहली स्ट्रिंग की लंबाई दूसरी से अधिक है, और हमें जांचना है कि पहली स्ट्रिंग के सबस्ट्रिंग्स दूसरी स्ट्रिंग से पूरी तरह मेल खाते हैं या केवल एक पोजीशन पर भिन्न हैं। हम पहली स्ट्रिंग के उन इंडेक्स लौटाते हैं जहां से ऐसे सबस्ट्रिंग्स शुरू होते हैं।

उदाहरण के लिए, यदि इनपुट है string1 = 'tpoint', string2 = 'pi', तो आउटपुट होगा 1 2।

पहली स्ट्रिंग के सबस्ट्रिंग्स जो दूसरी स्ट्रिंग से मेल खाते हैं या एक पोजीशन पर भिन्न हैं, इंडेक्स 1 और 2 पर 'po' और 'oi' हैं।

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

इस समस्या को हल करने के लिए हम Z-एल्गोरिथ्म का उपयोग करते हैं, जो स्ट्रिंग मिलान के लिए कुशल है। मुख्य चरण इस प्रकार हैं:

• search() फंक्शन परिभाषित करें जो दो स्ट्रिंग्स लेता है और Z-एरे की गणना करता है।
• दोनों स्ट्रिंग्स को जोड़कर (str_cat = string1 + string2) Z-एरे बनाएं।
• फॉरवर्ड (fwd) और बैकवर्ड (bwrd) दिशाओं में Z-मानों की गणना करें।
• दोनों दिशाओं के मानों को जोड़कर वैध शुरुआती इंडेक्स निर्धारित करें।

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

def search(string1, string2):
    str_cat = string1 + string2
    z_list = [0] * len(str_cat)
    z_list[0] = len(str_cat)
    right = 0
    left = 0
    for i in range(1, len(str_cat)):
        if i > right:
            j = 0
            while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
                j += 1
            z_list[i] = j
            if j > 0:
                left = i
                right = i + j - 1
        else:
            k = i - left
            r_len = right - i + 1
            if z_list[k] < r_len:
                z_list[i] = z_list[k]
            else:
                m = right + 1
                while m < len(str_cat) and str_cat[m] == str_cat[m - i]:
                    m += 1
                z_list[i] = m - i
                left = i
                right = m - 1
        z_list[i] = min(len(string1), z_list[i])
    return z_list[len(string1):]

def solve(str1, str2):
    fwd = search(str2, str1)
    bwrd = search(str2[::-1], str1[::-1])
    bwrd.reverse()
    idx = []
    for i in range(len(str1) - len(str2) + 1):
        if fwd[i] + bwrd[i + len(str2) - 1] >= len(str2) - 1:
            idx.append(str(i))
    if len(idx) == 0:
        return False
    else:
        return " ".join(idx)

print(solve('tpoint', 'pi'))

इनपुट

'tpoint', 'pi'

आउटपुट

1 2