제출 #1171074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171074		Ahmed57	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	544 ms	131072 KiB

necklace

#include <bits/stdc++.h>

using namespace std;
struct Hash{
    long long a = 41 , mod = 972663749;
    long long h[3001],p[3001];
    void buld(){
        p[0] = 1;
        for(int i = 1;i<=3000;i++){
            p[i] = (p[i-1]*a)%mod;
        }
    }
    void has(string s){
        h[0] = 0;
        for(int i = 0;i<s.size();i++){
            h[i+1] = (h[i]*a+((s[i]-'a')+1))%mod;
        }
    }
    long long q(int l,int r){return(((h[r]-h[l-1]*p[r-l+1])%mod)+mod)%mod;}
}hsh1,hsh2,hsh3;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    string a,b;
    cin>>a>>b;
    hsh1.buld();
    hsh2.buld();
    hsh1.has(a);
    hsh2.has(b);
    string B = b;
    reverse(B.begin(),B.end());
    hsh3.buld();
    hsh3.has(B);
    int n = a.size();
    n = max(n,(int)b.size());n+=1;
    unordered_map<int,int> mp[n];
    int lenB = b.size();
    for(int i = 0;i<b.size();i++){
        for(int j = i;j<b.size();j++){
            mp[j-i+1][hsh2.q(i+1,j+1)] = i+1;
            mp[j-i+1][hsh3.q(lenB-j,lenB-i)] = i+1;
        }
    }
    int st1 = -1 , st2 = -1;
    int ans = 0;
    for(int i = 0;i<a.size();i++){
        for(int j = i;j<a.size();j++){
            if(mp[j-i+1][hsh1.q(i+1,j+1)]){
                if(ans<j-i+1){
                    ans = j-i+1;
                    st1 = i+1;
                    st2 = mp[j-i+1][hsh1.q(i+1,j+1)];
                }
            }
            for(int e = i+1;e<=j;e++){
                long long lol1 = hsh1.q(i+1,e);
                long long lol2 = hsh1.q(e+1,j+1);
                lol2*=hsh1.p[e-i];
                lol2%=hsh1.mod;
                if(mp[j-i+1][(lol1+lol2)%hsh1.mod]){
                    if(ans<j-i+1){
                        ans = j-i+1;
                        st1 = i+1;
                        st2 = mp[j-i+1][(lol1+lol2)%hsh1.mod];
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    cout<<st1-1<<" "<<st2-1<<endl;
}

• Subtask 1: 0 / 15