পাইথনে স্ট্রিং-এ সিমিলার সাবস্ট্রিং কাউন্ট করে কোয়েরি আন্সার করার প্রোগ্রাম

দুটি স্ট্রিং s এবং কোয়েরি সেট Q দেওয়া আছে। Q[i] = (l, r)। s[l..r]-এর সাথে সিমিলার কতগুলো সাবস্ট্রিং s[x..y] আছে সেটি বের করুন। دو স্ট্রিং সিমিলার হলে:

1. দৈর্ঘ্য সমান
2. সব (i,j) পেয়ারের জন্য: s[i]==s[j] ⇔ t[i]==t[j]

উদাহরণ

s = "hjhhbcbk", Q = [(1,2), (2,4)] → আউটপুট: [6, 1]

এলগরিদম (ফিঙ্গারপ্রিন্ট + ব্রুট ফোর্স)

1. calc_fingerprint(s): প্রতিটি ক্যারেক্টারের প্রথম~Occurrence-র ইনডেক্স দিয়ে একটি ফিঙ্গারপ্রিন্ট বানান।
2. প্রতিটি কোয়েরির জন্য:
   • s1 := s[a-1:b]
   • সব সম্ভাব্য s2 চেক করুন ফিঙ্গারপ্রিন্ট এবং ক্যারেক্টার ম্যাপিং দিয়ে।

পাইথন কোড

fp = []

def calc_fingerprint(s):
    dict = {s[0]: 0}
    fp = "0"
    j = 1
    for i in range(1, len(s)):
        if s[i] not in dict:
            dict[s[i]], j = j, j+1
        fp += str(dict[s[i]])
    return int(fp)

def solve(s, Q):
    if len(s) > 10:
        for i in range(0, len(s)-10):
            fp.append(calc_fingerprint(s[i:i+10]))
    ret = []
    for a, b in Q:
        s1 = s[a-1:b]
        k = 0
        for i in range(len(s) - (b-a)):
            if b-a > 9 and fp[a-1] != fp[i]:
                continue
            dict = {}
            s2 = s[i:i+(b-a)+1]
            for i in range(b-a+1):
                if s2[i] not in dict:
                    if s1[i] in dict.values():
                        break
                    dict[s2[i]] = s1[i]
                if dict[s2[i]] != s1[i]:
                    break
            else:
                k += 1
        ret.append(k)
    return ret

s = "hjhhbcbk"
Q = [(1,2), (2,4)]
print(solve(s, Q))  # আউটপুট: [6, 1]

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

"hjhhbcbk", [(1,2), (2,4)]
[6, 1]