পাইথনে একটি স্ট্রিং এবং এর সাবস্ট্রিংগুলোর মোট সাদৃশ্য খুঁজে বের করার প্রোগ্রাম

আমাদের একটি স্ট্রিং s আছে। আমাদের s-এর প্রতিটি সাফিক্সের সাথে s-এর সাদৃশ্যের যোগফল বের করতে হবে। এখানে দুটি স্ট্রিংর মধ্যকার সাদৃশ্য বলতে দীর্ঘতম কমন প্রিফিক্সের দৈর্ঘ্যকে বোঝায়।

উদাহরণস্বরূপ, ইনপুট s = "pqpqpp" হলে আউটপুট হবে 11 কারণ স্ট্রিংটির সাফিক্সগুলো হলো "pqpqpp", "qpqpp", "pqpp", "qpp", "pp" এবং "p"। এই সাবস্ট্রিংগুলোর "pqpqpp"-এর সাথে সাদৃশ্য যথাক্রমে 6, 0, 3, 0, 1, এবং 1। তাই যোগফল = 6 + 0 + 3 + 0 + 1 + 1 = 11।

সমাধানের ধাপসমূহ (Z-অ্যালগরিদম)

• length := s-এর আকার

• total := length

• z := [0] দিয়ে একটি লিস্ট শুরু করুন

• l := 0, r := 0

• k = 1 থেকে length - 1 পর্যন্ত লুপ চালান:

  • যদি k > r হয়, তবে:

    • match := 0

    • index := k

  • index < length থাকাকালীন লুপ চালান:

    • যদি s[index] == s[match] হয়, তবে:

      • match := match + 1

      • index := index + 1

    • অন্যথায়, লুপ থেকে বেরিয়ে আসুন

  • match-কে z-এর শেষে যোগ করুন

  • যদি match > 0 হয়, তবে:

    • total := total + match

    • l := k

    • r := index - 1

  • অন্যথায়:

    • যদি z[k-l] < (r-k)+1 হয়, তবে:

      • z[k-l]-কে z-এর শেষে যোগ করুন

      • total := total + z[k-l]

    • অন্যথায়:

      • match := r - k

      • index := r

      • index < length থাকাকালীন লুপ চালান:

        • যদি s[index] == s[match] হয়, তবে:

          • match := match + 1

          • index := index + 1

        • অন্যথায়, লুপ থেকে বেরিয়ে আসুন

      • match-কে z-এর শেষে যোগ করুন

      • total := total + match

      • l := k

      • r := index - 1

• total রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(s):
    length = len(s)
    total = length
    z = [0]
    l = 0
    r = 0
    for k in range(1, length):
        if k > r:
            match = 0
            index = k
            while index < length:
                if s[index] == s[match]:
                    match += 1
                    index += 1
                else:
                    break
        z.append(match)
        if match > 0:
            total += match
            l = k
            r = index - 1
        else:
            if z[k-l] < (r-k) + 1:
                z.append(z[k-l])
                total += z[k-l]
            else:
                match = r - k
                index = r
                while index < length:
                    if s[index] == s[match]:
                        match += 1
                        index += 1
                    else:
                        break
                z.append(match)
                total += match
                l = k
                r = index - 1
    return total

s = "pqpqpp"
print(solve(s))

ইনপুট

"pqpqpp"

আউটপুট

11