C++ এ স্বতন্ত্র ইকো সাবস্ট্রিং

ধরুন আমাদের একটি স্ট্রিং S আছে; আমাদেরকে S-এর স্বতন্ত্র অ-খালি সাবস্ট্রিংগুলির সংখ্যা খুঁজে বের করতে হবে যেগুলি নিজের সাথে কিছু স্ট্রিং এর সংমিশ্রণ হিসাবে লেখা যেতে পারে।

সুতরাং, যদি ইনপুটটি "elloelloello" এর মত হয়, তাহলে আউটপুট হবে 5, কারণ কিছু সাবস্ট্রিং যেমন "ello", "lloe", "loel", "oell" আছে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• prime :=31

• m :=1^9 + 7

• একটি ফাংশন সংজ্ঞায়িত করুন fastPow(), এটি বেস, পাওয়ার,

  নেবে

• res :=1

• যখন শক্তি> 0, do −

  • যদি শক্তি এবং 1 অ-শূন্য হয়, তাহলে −

    • res :=res * base

    • res :=res mod m

  • base :=base * base

  • বেস :=বেস মোড m

  • power =power / 2

• রিটার্ন রিটার্ন

• CreateHashValue() একটি ফাংশন সংজ্ঞায়িত করুন, এটি s, n,

  লাগবে

• ফলাফল :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • ফলাফল :=ফলাফল + (s[i] * fastPow(prime, i))

  • ফলাফল :=ফলাফল মোড m

• ফেরত ফলাফল

• একটি ফাংশন সংজ্ঞায়িত করুন recalculateHash(), এটি পুরানো, নতুনC, oldHash, patLength,

  লাগবে

• newHash :=oldHash - পুরাতন

• newHash :=newHash * fastPow(prime, m - 2)

• newHash :=newHash + (newC * fastPow(prime, patlength - 1))

• newHash :=newHash mod m

• নতুন হ্যাশ ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• n :=পাঠ্যের আকার

• একটি সেট উত্তর সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=2, যখন i <=n, আপডেট i :=i + 2, do −

  • temp :=খালি স্ট্রিং

  • j শুরু করার জন্য :=0, যখন j করুন

    • temp :=temp + text[j]

  • hash1 :=createHashValue(temp, i/2)

  • temp :=খালি স্ট্রিং)

  • j শুরু করার জন্য :=i / 2, যখন j করুন

    • temp :=temp + text[j]

  • hash2 :=createHashValue(temp, i/2)

  • শুরু করার জন্য s1 :=0, e1 :=i / 2, s2 :=i / 2, e2 :=i, যখন e2

    • যদি হ্যাশ 1 হ্যাশ 2 এর মত হয়, তাহলে

      • উত্তরে হ্যাশ 1 সন্নিবেশ করান

    • hash1 :=recalculateHash(text[s1], text[e1], hash1, i / 2)

    • hash2 :=recalculateHash(text[s2], text[e2], hash2, i / 2)

  • যদি হ্যাশ 1 হ্যাশ 2 এর মত হয়, তাহলে

    • উত্তরে হ্যাশ 1 সন্নিবেশ করান

• উত্তরের রিটার্ন সাইজ

#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