ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে, আমাদেরকে s-এর একটি খালি সাবস্ট্রিং নির্বাচন করতে এবং একটি একক অক্ষরকে অন্য একটি ভিন্ন অক্ষর দ্বারা প্রতিস্থাপন করতে পারি এমন উপায়গুলি খুঁজে বের করতে হবে যাতে ফলস্বরূপ সাবস্ট্রিংটি টি-এর একটি সাবস্ট্রিং। উপরের শর্তটি পূরণ করে এমন সাবস্ট্রিংগুলির সংখ্যা আমাদের খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি s ="sts" t ="tsts" এর মত হয়, তাহলে আউটপুট হবে 6 কারণ নিম্নলিখিতগুলি হল s এবং t থেকে সাবস্ট্রিংগুলির জোড়া যা 1 অক্ষর দ্বারা পৃথক -
- ("sts", "tsts"),
- ("sts", "tsts"),
- ("sts", "tsts"),
- ("sts", "tsts"),
- ("sts", "tsts"),
- ("sts", "tsts")
বোল্ড অক্ষর অংশগুলি হল সাবস্ট্রিং যা দুটি স্ট্রিং s এবং t থেকে বেছে নেওয়া হয়।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n1 :=s এর আকার
- n2 :=t এর আকার
- উত্তর :=0
- s থেকে প্রতিটি সূচক i1 এবং অক্ষর c1 এর জন্য, করুন
- প্রতিটি সূচী i2 এবং t থেকে c2 অক্ষরের জন্য, করুন
- i :=i1, j :=i2
- যখন i
- i :=i + 1, j :=j + 1
- যদি i
- :=i + 1, j :=j + 1
- উত্তর :=উত্তর + ১
- যখন i
- i :=i + 1, j :=j + 1
- উত্তর :=উত্তর + ১
- প্রতিটি সূচী i2 এবং t থেকে c2 অক্ষরের জন্য, করুন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(s, t): n1 = len(s) n2 = len(t) ans = 0 for i1, c1 in enumerate(s): for i2, c2 in enumerate(t): i = i1 j = i2 while i < n1 and j < n2 and s[i] == t[j]: i += 1 j += 1 if i < n1 and j < n2 and s[i] != t[j]: i += 1 j += 1 ans += 1 while i < n1 and j < n2 and s[i] == t[j]: i += 1 j += 1 ans += 1 return ans s = "sts" t = "tsts" print(solve(s, t))
ইনপুট
"sts", "tsts"
আউটপুট
6