Submission #1343144

#TimeUsernameProblemLanguageResultExecution timeMemory
1343144Jakub_WozniakNecklace (Subtask 1-3) (BOI19_necklace1)C++20
45 / 85
1594 ms652 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define st first
#define nd second
int N , N1 , N2;
string s1 , s2;
int maxi = 0;
pii Par = {-1,-1};
bool czyneg = 0;
const int maxn = 3009;
const ll mod[2] = {(ll)(1e+9)+7 , (ll)(1e+9)+9};
ll H[maxn][2][2];
ll P[maxn][2];

ll hasz(int l , int r , int c)
{
    ll H0 = (H[r][0][c]-H[l-1][0][c]+mod[0])%mod[0]*P[N-l][0]%mod[0];   
    ll H1 = (H[r][1][c]-H[l-1][1][c]+mod[1])%mod[1]*P[N-l][1]%mod[1];
    return H0*mod[1] + H1;   
}

unordered_map <ll , int> Um;

void sprawdz(bool czyr)
{
    P[0][0] = 1;
    for(int i = 1; i <= N+23 ; i++)P[i][0] = (P[i-1][0]*119)%mod[0];
    P[0][1] = 1;
    for(int i = 1; i <= N+23 ; i++)P[i][1] = (P[i-1][1]*119)%mod[1];

    for(int i = 1; i <= N1 ; i++)
    {
        H[i][0][0] = (H[i-1][0][0] + (s1[i]-'a'+1)*P[i][0])%mod[0];
        H[i][1][0] = (H[i-1][1][0] + (s1[i]-'a'+1)*P[i][1])%mod[1];
    }
    for(int i = 1; i <= N2 ; i++)
    {
        H[i][0][1] = (H[i-1][0][1] + (s2[i]-'a'+1)*P[i][0])%mod[0];
        H[i][1][1] = (H[i-1][1][1] + (s2[i]-'a'+1)*P[i][1])%mod[1];
    }

    for(int k = 0 ; k < min(N1,N2) ; k++)
    {
        Um.clear();
        for(int i = 1; i+k <= N1 ; i++)
        {
            Um[hasz(i,i+k,0)] = i;
        }

        for(int j = 1 ; j+k <= N2 ; j++)
        {
            if(Um[hasz(j,j+k,1)] != 0)
            {
                if(k+1 > maxi)
                {
                    Par = {Um[hasz(j,j+k,1)],j};
                    czyneg = czyr;
                }
                maxi = max(maxi , k+1);
            }
        } 
    }


    int ileS;
    if(maxi > 0)ileS = N*N/maxi*15;
    else ileS = N*N*15;

    while(ileS--)
    {
        int i = rand()%N1+1 , j = rand()%N2+1;
        if(s1[i] != s2[j])continue;
        int l0 = i , r0 = i , l1 = j , r1 = j;

        while(l0 > 1 && l1 > 1 && s1[l0-1] == s2[l1-1])
        {
            l0--;
            l1--;
        }

        while(r0 <= N1 && r1 <= N2 && s1[r0] == s2[r1])
        {
            r0++;
            r1++;
        }

        // przedzilay [l0,r0) i [l1,r1) sa ok

        int akti = -N-3;
        for(int k1 = 0 ; k1+r0 <= N1 && l1-k1-1 >= 1 && k1 <= (r0-l0)+1; k1++)
        {
            if(hasz(r0,r0+k1,0) == hasz(l1-k1-1,l1-1,1))akti = k1;
        }
        if(maxi < (r0-l0)+(akti+1))
        {
            Par = {l0,l1-akti-1};
            czyneg = czyr;
        }
        maxi = max(maxi , (r0-l0)+(akti+1));

        akti = -N-3;
        for(int k1 = 0 ; k1+r1 <= N2 && l0-k1-1 >= 1 && k1 <= (r0-l0)+1; k1++)
        {
            if(hasz(r1,r1+k1,1) == hasz(l0-k1-1,l0-1,0))akti = k1;
        }
        if(maxi < (r1-l1)+(akti+1))
        {
            Par = {l0-akti-1,l1};
            czyneg = czyr;
        }
        maxi = max(maxi , (r0-l0)+(akti+1));

        if(maxi == 0)continue;
        ileS = min(ileS , N*N/maxi*15);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s1 >> s2;
    N1 = s1.size();
    N2 = s2.size();
    N = max(N1,N2);
    s1 = '$'+s1+'$';
    s2 = '$'+s2+'$';

    sprawdz(0);
    reverse(s2.begin() , s2.end());
    sprawdz(1);

    cout << maxi << '\n';
    cout << Par.st-1 << ' ';
    if(czyneg)
    {
        cout << N2-Par.nd+1 - maxi << '\n';
    }
    else cout << Par.nd-1 << '\n';



    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...