C++での個別のエコー部分文字列

理解を深めるために、次の実装を見てみましょう-

例

#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