Submission #1235877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235877		shjeong	Joyful KMP (KRIII5_JK)	C++20	2 / 1	224 ms	133736 KiB

JK

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e9;
ll n, k;
string s;
struct UF{
    vector<ll> p;
    UF(): p(1010101,-1){}
    ll find(ll x){ if(p[x]<0)return x; return p[x] = find(p[x]); }
    void merge(ll x, ll y){
        x=find(x),y=find(y);
        if(x==y)return; p[x]+=p[y]; p[y]=x;
    }
} uf;
vector<ll> adj[1010101], ADJ[1010101];
vector<ll> getfail(string &s){
    ll n = sz(s);
    vector<ll> fail(n);
    for(int i = 1, j = 0 ; i < n ; i++){
        while(j>0 and s[i]^s[j]){
            adj[i].push_back(j); adj[j].push_back(i);
            j=fail[j-1];
        }
        if(s[i]==s[j])uf.merge(j,i), fail[i] = ++j;
        else adj[i].push_back(j), adj[j].push_back(i);
    }
    return fail;
}
ll ans = 1;
bool vis[1010101];
void dfs(ll x){
    ll c = 0;
    for(auto next : ADJ[x])c+=vis[next];
    ans = ans*(26-c)%MOD;
    vis[x]=1;
    for(auto next : ADJ[x])if(!vis[next])dfs(next);
}
int main(){
    fast;
    cin>>s>>k; n = sz(s);
    getfail(s);
    for(int i = 0 ; i < n ; i++){
        for(auto j : adj[i])ADJ[uf.find(i)].push_back(uf.find(j));
    }
    for(int i = 0 ; i < n ; i++)sort(all(ADJ[i])), COMP(ADJ[i]);
    for(int i = 0 ; i < n ; i++)if(uf.find(i)==i and !vis[i])dfs(i);
    cout<<ans<<"\n";
    cout<<"OVER\n";
}

• Subtask 1: 2 / 1