Substring Echo ที่แตกต่างกันใน C++

คำอธิบายโจทย์

หาจำนวน substring ที่ไม่ซ้ำกัน ซึ่งเป็นการต่อ string กับตัวเอง (s = t+t) เช่น "ello" = "el"+"lo" ไม่ใช่ แต่ "elloello" = "ello"+"ello" ใช่

ตัวอย่าง

"elloelloello" → Output: 5

Substrings: "ello", "lloe", "loel", "oell" (และอีก 1 ตัว)

วิธีแก้ปัญหา

ใช้ Rolling Hash (Rabin-Karp) ตรวจสอบ substring ความยาวคู่:

ลองความยาว i = 2,4,6... จนครอบคลุม string
คำนวณ hash ของครึ่งแรกและครึ่งหลังของ window ขนาด i
เลื่อน window คำนวณ hash ใหม่แบบ O(1) ด้วย recalculateHash
เก็บ hash ที่ตรงกันใน set ป้องกันซ้ำ

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli prime = 31;
const lli MOD = 1e9 + 7;

class Solution {
public:
    lli fastPow(lli base, lli power) {
        lli res = 1;
        while(power > 0) {
            if(power & 1) { res = res*base % MOD; }
            base = base*base % MOD;
            power >>= 1;
        }
        return res;
    }
    
    lli createHashValue(string s, lli n) {
        lli result = 0;
        for(lli i=0; i

อินพุต
"elloelloello"

เอาต์พุต
5