随机三模数哈希

#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))
typedef long long ll ;

const int N = 1e6 + 7 ; const ll p = 998244353ll ,base = 131ll ;
char s[N] ,t[N] ; ll ls ,lt ,loc[N] ,dp[N] ,g[N] ,ans[N] ,c[N] ;
ll pr[150] = {0ll ,899997011ll ,899997019ll ,899997029ll ,899997041ll ,899997047ll ,899997089ll ,899997097ll ,
899997113ll ,899997167ll ,899997173ll ,899997179ll ,899997229ll ,899997247ll ,899997271ll ,899997283ll ,899997317ll ,
899997359ll ,899997401ll ,899997419ll ,899997421ll ,899997451ll ,899997463ll ,899997473ll ,899997479ll ,899997499ll ,
899997503ll ,899997523ll ,899997559ll ,899997587ll ,899997589ll ,899997619ll ,899997661ll ,899997671ll ,899997677ll ,
899997701ll ,899997737ll ,899997739ll ,899997743ll ,899997773ll ,899997779ll ,899997781ll ,899997827ll ,899997841ll ,
899997863ll ,899997883ll ,899997887ll ,899997911ll ,899997949ll ,899997961ll ,899997991ll ,899998013ll ,899998019ll ,
899998049ll ,899998051ll ,899998063ll ,899998097ll ,899998103ll ,899998109ll ,899998117ll ,899998157ll ,899998163ll ,
899998181ll ,899998193ll ,899998271ll ,899998273ll ,899998313ll ,899998367ll ,899998373ll ,899998387ll ,899998391ll ,
899998399ll ,899998409ll ,899998439ll ,899998457ll ,899998481ll ,899998501ll ,899998523ll ,899998537ll ,899998553ll ,
899998559ll ,899998597ll ,899998601ll ,899998607ll ,899998613ll ,899998639ll ,899998661ll ,899998663ll ,899998679ll ,
899998691ll ,899998709ll ,899998733ll ,899998753ll ,899998811ll ,899998843ll ,899998861ll ,899998909ll ,899998919ll ,
899998927ll ,899998937ll ,899998961ll ,899999003ll ,899999029ll ,899999033ll ,899999041ll ,899999069ll ,899999071ll ,
899999119ll ,899999123ll ,899999143ll ,899999167ll ,899999173ll ,899999197ll ,899999231ll ,899999281ll ,899999299ll ,
899999333ll ,899999341ll ,899999357ll ,899999371ll ,899999389ll ,899999423ll ,899999437ll ,899999483ll ,899999531ll ,
899999537ll ,899999539ll ,899999549ll ,899999557ll ,899999609ll ,899999701ll ,899999741ll ,899999743ll ,899999759ll ,
899999777ll ,899999797ll ,899999801ll ,899999813ll ,899999911ll ,899999921ll ,899999929ll ,899999963ll} ;

inline int myrand (int l ,int r) {
    int rnd = std :: rand () << 15 | std :: rand () ;
    if (rnd < 0) rnd = - rnd ;
    return rnd % (r - l + 1) + l ;
}

class good_hash {
private :
    ll mod ,hs[N] ,ht[N] ,pw[N] ,qp[30] ;
    std :: bitset < 900000001 > se ;

    inline ll hash (int l ,int r) 
    { return (hs[r] - hs[l - 1] * pw[r - l + 1] % mod + mod) % mod ;}

    inline ll qpow (ll base) {
        ll p = mod - 2ll ,res = 1ll ;
        while (p) {
            if (p & 1ll) (res *= base) %= mod ;
            (base *= base) %= mod ;
            p >>= 1ll ;
        } return res ;
    } 

public :
    inline void pre () {
        mod = pr[myrand (1 ,141)] ;

        f (i ,1 ,ls ,1) 
            hs[i] = (hs[i - 1] * base % mod + s[i]) % mod ;
        f (i ,1 ,lt ,1) 
            ht[i] = (ht[i - 1] * base % mod + t[i]) % mod ;

        pw[0] = 1ll ;
        f (i ,1 ,ls ,1) 
            pw[i] = pw[i - 1] * base % mod ;

        ll cur ; se[cur = 1ll] = 1 ;
        f (i ,1 ,ls ,1) 
            se[cur = cur * base % mod] = 1 ;

        f (i ,1 ,25 ,1) 
            qp[i] = qpow (i) ;
    }

    inline bool judge (int l ,int r) {
        int len = r - l + 1 ;
        ll ha = hash (l ,r) ;
        if (ha == ht[len]) return true ;

        ll ha_ = ha ; ha = (ha - ht[len] + mod) % mod ;
        f (i ,1 ,25 ,1) 
            if (se[ha * qp[i] % mod] == 1) return true ;
        ha = (ht[len] - ha_ + mod) % mod ;
        f (i ,1 ,25 ,1)
            if (se[ha * qp[i] % mod] == 1) return true ;
        return false ;
    }
} h1 ,h2 ,h3 ;

inline bool judge (int ,int) ;

int main () {
    std :: srand (std :: time (0)) ;

    std :: cin >> s + 1 >> t + 1 ;
    ls = std :: strlen (s + 1) ,lt = std :: strlen (t + 1) ;
    h1.pre () ,h2.pre () ,h3.pre () ;
    
    int l = 1 ,r = std :: min (lt ,ls) ,res ; 
    while (l <= r) {
        int mid = l + r >> 1 ;
        if (judge (1 ,mid)) 
            l = mid + 1 ,res = mid ;
        else r = mid - 1 ;
    } c[1] ++ ; c[res + 1] = p - 1 ;
    int cur = 1 ; ll tot = 0ll ; 
    loc[1] = res ;
    f (i ,1 ,ls - 1 ,1) {
        while (cur <= i) (tot += c[cur ++] + p) %= p ;
        dp[i] = tot ;
        int l = i + 1 ,r = std :: min (ls ,i + lt) ,res ;
        while (l <= r) {
            int mid = l + r >> 1 ;
            if (judge (i + 1 ,mid)) 
                l = mid + 1 ,res = mid ;
            else r = mid - 1 ;
        } loc[i + 1] = res ;
        //std :: cout << i + 1 << ' ' << res << '\n' ;
        (c[i + 1] += dp[i] + p) %= p ; 
        (c[loc[i + 1] + 1] += p - dp[i]) %= p ;
    } (tot += c[cur] + p) %= p ; 
    dp[ls] = tot ;

    //puts ("111111") ;
    
    memset (c ,0 ,sizeof c) ;
    c[1] ++ ; c[loc[1] + 1] = p - 1 ;
    cur = 1 ; tot = 0ll ;
    f (i ,1 ,ls - 1 ,1) {
        while (cur <= i) (tot += c[cur ++] + p) %= p ;
        g[i] = tot ;
        (c[i + 1] += dp[i] + g[i] + p) %= p ; 
        (c[loc[i + 1] + 1] += (p << 1) - dp[i] - g[i]) %= p ;
    } (tot += c[cur] + p) %= p ;
    g[ls] = tot ;

    memset (c ,0 ,sizeof c) ;
    c[1] ++ ; c[loc[1] + 1] = p - 1 ;
    cur = 1 ,tot = 0ll ;
    f (i ,1 ,ls - 1 ,1) {
        while (cur <= i) (tot += c[cur ++] + p) %= p ;
        ans[i] = tot ;
        (c[i + 1] += dp[i] + ans[i] + (g[i] << 1) + p) %= p ;
        (c[loc[i + 1] + 1] += (p << 2) - dp[i] - ans[i] - (g[i] << 1)) %= p ;
    } (tot += c[cur] + p) %= p ;
    ans[ls] = tot ;
    std :: cout << ans[ls] << '\n' ;
    return 0 ;
}

inline bool judge (int l ,int r) 
{ return h1.judge (l ,r) && h2.judge (l ,r) && h3.judge (l ,r) ;}