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

ধরুন আমাদের একটি স্ট্রিং str দেওয়া আছে। একটি স্ট্রিংর বর্ডার হলো একটি সাবস্ট্রিং যা স্ট্রিংটির প্রপার প্রিফিক্স এবং সাফিক্স দুটোই। উদাহরণস্বরূপ, 'ab' হলো 'ababab' স্ট্রিংর একটি বর্ডার। একটি বর্ডারকে প্যালিনড্রোমিক বর্ডার বলা হয় যদি বর্ডার স্ট্রিংটি প্যালিনড্রোম হয়। এখন ধরুন f(str) হলো দেওয়া স্ট্রিং str-এ প্যালিনড্রোমিক বর্ডারের সংখ্যা। আমাদের বের করতে হবে সব নন-ইম্পটি সাবস্ট্রিং str_k এর জন্য f(str_k)-এর যোগফল। যোগফলটি বড় হতে পারে, তাই 10^9 + 7 দিয়ে মডুলো অপারেশন করা যাবে।

উদাহরণস্বরূপ, যদি ইনপুট str = 'pqpqp' হয়, তবে আউটপুট হবে 5। স্ট্রিং 'pqpqp'-এর ১৫টি সাবস্ট্রিং আছে; কিন্তু শুধু ৪টি সাবস্ট্রিংয়ের প্যালিনড্রোমিক বর্ডার আছে। স্ট্রিংগুলো হলো:

pqp : f(pqp) = 1
pqpqp : f(pqpqp) = 2
qpq : f(qpq) = 1
pqp : f(pqp) = 1
যোগফল = 1 + 2 + 1 + 1 = 5

সমাধানের ধাপসমূহ

palindrome_calculator() ফাংশন ডিফাইন করুন যা input_dict নেবে
str_check() ফাংশন ডিফাইন করুন যা স্ট্রিং নেবে এবং সব ক্যারেক্টার একই কিনা চেক করবে
string_res() ফাংশন ডিফাইন করুন যা স্ট্রিং নেবে এবং ফর্মুলা ব্যবহার করে রেজাল্ট বের করবে
অড এবং ইভেন দৈর্ঘ্যের প্যালিনড্রোম আলাদা আলাদা হ্যান্ডেল করুন
ডাইনামিক প্রোগ্রামিং অ্যাপ্রোচ ব্যবহার করে সব সাবস্ট্রিং চেক করুন

উদাহরণ

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

def palindrome_calculator(input_dict):
    ans = 0
    for item1, item2 in input_dict.items():
        ans += item2 * (item2 - 1) // 2
    return ans

def str_check(string):
    t_str = string[0]
    for s in string:
        if s != t_str:
            return False
    return True

def string_res(string):
    ans = 0
    for i in range(2, len(string) + 1):
        ans += i * (i - 1) // 2
        ans %= 1000000007
    return ans

def solve(string):
    if str_check(string):
        return string_res(string)
    ans = 0
    odd_list = [[], {}, 1]
    for s in string:
        if s not in odd_list[1]:
            odd_list[1][s] = 0
        odd_list[1][s] += 1
    for i in range(len(string)):
        odd_list[0].append(i)
    ans += palindrome_calculator(odd_list[1])
    even_list = [[], {}, 1]
    for i in range(len(string) - 1):
        if string[i] == string[i + 1]:
            even_list[0].append(i)
            tmp = string[i:i + 2]
            if tmp not in even_list[1]:
                even_list[1][tmp] = 0
            even_list[1][tmp] += 1
    ans += palindrome_calculator(even_list[1])
    for val in range(3, len(string)):
        if val % 2 == 0:
            wt = even_list
        else:
            wt = odd_list
        new_t = [[], {}, val]
        for index in wt[0]:
            if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
                new_t[0].append(index - 1)
                tmp = string[index - 1 : index - 1 + val]
                if tmp not in new_t[1]:
                    new_t[1][tmp] = 0
                new_t[1][tmp] += 1
        ans += palindrome_calculator(new_t[1])
        ans %= 1000000007
        if val % 2 == 0:
            even_list = new_t
        else:
            odd_list = new_t
    return ans

print(solve('pqpqp'))

ইনপুট

'pqpqp'