ধরি S একটি স্ট্রিং। আমাদের S-এর সকল ভিন্ন নন-ইম্পটি সাবস্ট্রিং গণনা করতে হবে যেগুলো নিজের সাথে নিজের সংযোজন (concatenation) হিসেবে লেখা যায়।
ইনপুট যদি "elloelloello" হয়, তবে আউটপুট 5, কারণ "ello", "lloe", "loel", "oell" এর মতো সাবস্ট্রিং আছে।
সমাধানের ধাপসমূহ
prime := 31, m := 10^9 + 7
fastPow() ফাংশন সংজ্ঞায়িত করুন যা বেস এবং পাওয়ার নেবে – মডুলার এক্সপোনেনশিয়েশন করবে
createHashValue() ফাংশন সংজ্ঞায়িত করুন যা স্ট্রিং s এবং দৈর্ঘ্য n নেবে – রোলিং হ্যাশ তৈরি করবে
recalculateHash() ফাংশন সংজ্ঞায়িত করুন যা পুরনো ক্যারেক্টার, নতুন ক্যারেক্টার, পুরনো হ্যাশ, প্যাটার্ন দৈর্ঘ্য নেবে – নতুন হ্যাশ ক্যালকুলেট করবে
মূল পদ্ধতিতে –
n := text এর আকার
ans নামক একটি সেট সংজ্ঞায়িত করুন
i := 2 থেকে n পর্যন্ত 2-য়ে বাড়িয়ে লুপ চালান –
প্রথম অর্ধেক এবং দ্বিতীয় অর্ধেকের হ্যাশ বের করুন
স্লাইডিং উইন্ডো দিয়ে সব পজিশনে হ্যাশ কমপেয়ার করুন
যদি হ্যাশ মিলে, তবে ans-এ ইনসার্ট করুন
ans-এর আকার ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli prime = 31; const lli m = 1e9 + 7; class Solution { public: lli fastPow(lli base, lli power){ lli res = 1; while (power > 0) { if (power & 1) { res = res * base; res %= m; } base *= base; base %= m; power >>= 1; } return res; } lli createHashValue(string s, lli n){ lli result = 0; for (lli i = 0; i < n; i++) { result += (lli)(s[i] * fastPow(prime, i)); result %= m; } return result; } lli recalculateHash(char old, char newC, lli oldHash, lli patLength){ lli newHash; newHash = oldHash - (lli)old; newHash *= fastPow(prime, m - 2); newHash += ((lli)newC * fastPow(prime, patLength - 1)); newHash %= m; return newHash; } int distinctEchoSubstrings(string text){ int n = text.size(); set<int> ans; for (int i = 2; i <= n; i += 2) { string temp = ""; for (int j = 0; j < i / 2; j++) { temp += text[j]; } int hash1 = createHashValue(temp, i / 2); temp = ""; for (int j = i / 2; j < i; j++) { temp += text[j]; } int hash2 = createHashValue(temp, i / 2); for (int s1 = 0, e1 = i / 2, s2 = i / 2, e2 = i; e2 < n; s1++, s2++, e1++, e2++) { if (hash1 == hash2) { ans.insert(hash1); } hash1 = recalculateHash(text[s1], text[e1], hash1, i / 2); hash2 = recalculateHash(text[s2], text[e2], hash2, i / 2); } if (hash1 == hash2) { ans.insert(hash1); } } return ans.size(); } }; main(){ Solution ob; cout << (ob.distinctEchoSubstrings("elloelloello")); }ইনপুট
"elloelloello"
আউটপুট
5
