제출 #1349350

#제출 시각아이디문제언어결과실행 시간메모리
1349350ahmadmakkiehNecklace (Subtask 4) (BOI19_necklace4)C++20
0 / 15
1595 ms1324 KiB
#include <bits/stdc++.h>
using namespace std;

// Booth's algorithm: index of the lexicographically smallest rotation
int least_rotation(const string& s) {
    int n = (int)s.size();
    string t = s + s;
    int i = 0, j = 1, k = 0;

    while (i < n && j < n && k < n) {
        char a = t[i + k], b = t[j + k];
        if (a == b) {
            ++k;
        } else if (a > b) {
            i += k + 1;
            if (i <= j) i = j + 1;
            k = 0;
        } else {
            j += k + 1;
            if (j <= i) j = i + 1;
            k = 0;
        }
    }
    return min(i, j);
}

string rotate_left(const string& s, int p) {
    int n = (int)s.size();
    p %= n;
    return s.substr(p) + s.substr(0, p);
}

// Canonical representative of the necklace:
// minimum among all rotations of s and all rotations of reverse(s)
string canonical(const string& s) {
    int p1 = least_rotation(s);
    string a = rotate_left(s, p1);

    string r = s;
    reverse(r.begin(), r.end());
    int p2 = least_rotation(r);
    string b = rotate_left(r, p2);

    return min(a, b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;

    int n = (int)s.size();
    int m = (int)t.size();

    for (int L = min(n, m); L >= 1; --L) {
        unordered_map<string, int> pos;
        pos.reserve(n * 2);
        pos.max_load_factor(0.7f);

        // Store one starting position for each necklace class in Jill's string
        for (int i = 0; i + L <= n; ++i) {
            string key = canonical(s.substr(i, L));
            if (!pos.count(key)) pos[key] = i;
        }

        // Look for a matching necklace class in Jane's string
        for (int j = 0; j + L <= m; ++j) {
            string key = canonical(t.substr(j, L));
            auto it = pos.find(key);
            if (it != pos.end()) {
                cout << L << '\n';
                cout << it->second << ' ' << j << '\n';
                return 0;
            }
        }
    }

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