Submission #672363

#	Time	Username	Problem	Language	Result	Execution time	Memory
672363		_martynas	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	25 / 85	1572 ms	372 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

ll MOD[2] = {1000000007, 1000000009};

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const ll X = 29;

const int MXN = 3005;

int n, m;
string a, b[2];

ll H_A[2][MXN], H[2][2][MXN];
ll XP[2][MXN];

ll get_a(int mod, int l, int r) {
    assert(l <= r);
    return (H_A[mod][r]-(l ? (H_A[mod][l-1]*XP[mod][r-l+1])%MOD[mod] : 0)+MOD[mod])%MOD[mod];
}

ll get_b(int mod, int k, int l, int r) {
    assert(l <= r);
    return (H[mod][k][r]-(l ? (H[mod][k][l-1]*XP[mod][r-l+1])%MOD[mod] : 0)+MOD[mod])%MOD[mod];
}

void init() {
    for(int mod = 0; mod < 2; mod++) {
        XP[mod][0] = 1;
        for(int i = 1; i <= max(n, m); i++) {
            XP[mod][i] = (X*XP[mod][i-1])%MOD[mod];
        }
        H_A[mod][0] = a[0]-'a'+1;
        for(int i = 1; i < n; i++) {
            H_A[mod][i] = (X*H_A[mod][i-1]+a[i]-'a'+1)%MOD[mod];
        }
        for(int k = 0; k < 2; k++) {
            H[mod][k][0] = b[k][0]-'a'+1;
            for(int i = 1; i < m; i++) {
                H[mod][k][i] = (X*H[mod][k][i-1]+b[k][i]-'a'+1)%MOD[mod];
            }
        }
    }
}

set<pair<ll, ll>> S;
pii check(int len) {
    // check if a[i..i+len]+a[i..i+len] contains b[j..j+len] or reverse b[j..j+len]
    for(int i = 0; i+len <= n; i++) {
        S.clear();
        // a0 a1 a2 a0 a1 a2
        // --------
        //    --------
        //       --------
        for(int j = 0; j < len; j++) {
            ll val[2];
            for(int mod = 0; mod < 2; mod++) {
                val[mod] = get_a(mod, i+j, i+len-1)*XP[mod][j]%MOD[mod];
                if(j) {
                    val[mod] += get_a(mod, i, i+j-1);
                }
            }
            //cerr << a.substr(i+j, (i+len-1)-(i+j)+1) << " + " << (j?a.substr(i, j):"") << "\n";
            S.insert(pll{val[0]%MOD[0], val[1]%MOD[1]});
        }

//        for(string s : stringS) {
//            cerr << s << "\n";
//        }

        for(int j = 0; j+len <= m; j++) {
            ll val[2];
            for(int mod = 0; mod < 2; mod++) {
                val[mod] = get_b(mod, 0, j, j+len-1);
            }
            auto it = S.find(pll{val[0], val[1]});
            if(it != S.end()) {
                return {i, j};
            }
        }
        for(int j = 0; j+len <= m; j++) {
            ll val[2];
            for(int mod = 0; mod < 2; mod++) {
                val[mod] = get_b(mod, 1, j, j+len-1);
            }
            auto it = S.find(pll{val[0], val[1]});
            if(it != S.end()) {
                return {i, m-(j+len-1)-1};
            }
        }
    }
    return {-1, -1};
}

int main() {
    //FASTIO();

    cin >> a >> b[0];
    n = a.size();
    m = b[0].size();
    cerr << "n = " << n << "\n";
    cerr << "m = " << m << "\n";
    b[1] = b[0];
    reverse(all(b[1]));

    init();
    for(int i = min(n, m); i >= 1; i--) {
        pii ans = check(i);
        if(ans.F != -1) {
            cout << i << "\n";
            cout << ans.F << " " << ans.S << "\n";
            break;
        }
    }

    return 0;
}

/*



*/

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40