সূচীগুলি খুঁজে বের করার প্রোগ্রাম যেখানে একটি স্ট্রিংয়ের সাবস্ট্রিংগুলি অন্য স্ট্রিংয়ের সাথে সম্পূর্ণ মেলে বা পাইথনের একটি অবস্থানে আলাদা

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

সুতরাং, যদি ইনপুট হয় string1 ='tpoint', string2 ='pi', তাহলে আউটপুট হবে 1 2।

প্রথম স্ট্রিং থেকে যে সাবস্ট্রিংটি দ্বিতীয় স্ট্রিংয়ের সাথে মিলে যায় বা সূচক 1 এবং 2-এ একটি অবস্থানে ভিন্ন হয় তা হল 'po' এবং 'oi'।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন অনুসন্ধান () সংজ্ঞায়িত করুন। এটি string1, string2
  লাগবে
  • str_cat :=string1 + string2
  • z_list :=str_cat এর আকারের একটি নতুন তালিকা 0 দিয়ে আরম্ভ করা হয়েছে
  • z_list[0] :=str_cat এর আকার
  • ডান :=0
  • বামে :=0
  • আমি রেঞ্জ 1 থেকে str_cat এর আকারের জন্য, কর
    • যদি আমি> সঠিক, তাহলে
      • j :=0
      • যদিও j + i
      • j :=j + 1
    • z_list[i] :=j
    • যদি j> 0 হয়, তাহলে
      • বামে :=i
      • ডান :=i + j - 1
  • অন্যথায়,
    • k :=i - বাকি
    • r_len :=ডান - i + 1
    • যদি z_list[k]
    • z_list[i] :=z_list[k]
  • অন্যথায়,
    • m :=ডান + 1
    • যদিও m
    • m :=m + 1
    • z_list[i] :=m - i
    • বামে :=i
    • ডান :=m - 1

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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