পাইথনে একটি স্ট্রিং-এর সাবস্ট্রিংগুলি যখন অন্য স্ট্রিং-এর সাথে পুরোপুরি মিলে বা এক পজিশনে ভিন্ন হয়, তাদের সূচক খুঁজে বের করার প্রোগ্রাম

দুটি স্ট্রিং দেওয়া আছে। প্রথম স্ট্রিংটির দৈর্ঘ্য দ্বিতীয়টির চেয়ে বড়। আমাদের চেক করতে হবে প্রথম স্ট্রিং-এর সাবস্ট্রিংগুলি দ্বিতীয় স্ট্রিং-এর সাথে সঠিকভাবে মিলে কিনা বা শুধু এক পজিশনে ভিন্ন হয় কিনা। আমরা প্রথম স্ট্রিং-এর সেই সূচকগুলি রিটার্ন করব যেখানে থেকে মিলে যাওয়া সাবস্ট্রিংগুলো শুরু হয়।

উদাহরণ

ইনপুট: string1 = 'tpoint', string2 = 'pi' → আউটপুট: 1 2

সূচক ১ এবং ২-এ প্রথম স্ট্রিং-এর সাবস্ট্রিং 'po' এবং 'oi' — যারা দ্বিতীয় স্ট্রিং 'pi' এর সাথে পুরোপুরি মিলে বা এক পজিশনে ভিন্ন।

এলগরিদম

1. search() ফাংশন সংজ্ঞায়িত করুন যা string1, string2 নেবে।
   • str_cat := string1 + string2
   • z_list := str_cat-এর আকারের একটি লিস্ট, সব মান ০ দিয়ে আরম্ভ করা।
   • z_list[0] := str_cat-এর আকার
   • right := 0, left := 0
   • i = 1 থেকে len(str_cat)-1 পর্যন্ত লুপ চালান:
     • যদি i > right হয়:
       • j := 0
       • while j+i < len(str_cat) and str_cat[j] == str_cat[j+i] — j++
       • z_list[i] := j
       • যদি j > 0 হয়: left := i, right := i+j-1
     • অন্যথায়:
       • k := i - left
       • r_len := right - i + 1
       • যদি z_list[k] < r_len হয়: z_list[i] := z_list[k]
       • অন্যথায়:
         • m := right + 1
         • while m < len(str_cat) and str_cat[m] == str_cat[m-i] — m++
         • z_list[i] := m - i, left := i, right := m-1
   • z_list[i] := min(len(string1), z_list[i])
   • z_list[len(string1):] রিটার্ন করুন
2. fwd := search(str2, str1)
3. bwrd := search(str2[::-1], str1[::-1]) → bwrd.reverse()
4. idx := []
5. i = 0 থেকে len(str1) - len(str2) পর্যন্ত:
   • যদি fwd[i] + bwrd[i + len(str2)-1] >= len(str2)-1 হয়: idx.append(str(i))
6. যদি idx খালি হয়: False রিটার্ন করুন, অন্যথায় " ".join(idx) রিটার্ন করুন।

পাইথন কোড

def search(string1, string2):
    str_cat = string1 + string2
    z_list = [0] * len(str_cat)
    z_list[0] = len(str_cat)
    right = 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, right = i, 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, right = i, 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))
    return " ".join(idx) if idx else False

print(solve('tpoint', 'pi'))  # আউটপুট: 1 2

ইনপুট / আউটপুট

'tpoint', 'pi'
1 2