제출 #1342981

#제출 시각아이디문제언어결과실행 시간메모리
1342981Jakub_WozniakNecklace (Subtask 1-3) (BOI19_necklace1)C++20
17 / 85
598 ms864 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);
            }
        } 
    }
    

    /*
    for(int i = 1 ; i <= N ; i++)
    {
        for(int j = 1 ; j <= N ; j++)
        {
            int L = 0 , R = 0;
            for(int k1 = 0 ; k1 <= min(i-1,(N-j-1)) ; k1++)
            {
                if(hasz(i-k1 , i, 0) == hasz(j+1,j+1+k1 , 1)) L = k1;
            }
            for(int k1 = 0 ; k1 <= min(j-1,(N-i-1)) ; k1++)
            {
                if(hasz(j-k1 , j, 1) == hasz(i+1,i+1+k1 , 0)) R = k1;
            }

            if(maxi < L+R)
            {
                Par = {i-L , j-R};
                czyneg = czyr;
            }
            maxi = max(maxi , L+R);
        }
    }
    */
}

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());
    s2 = '$'+s2;
    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...