Submission #621475

#	Time	Username	Problem	Language	Result	Execution time	Memory
621475		brobat	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	17 / 85	210 ms	35764 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

vector <int> kmp(string &a, string &b) {
    string s = b + '#' + a;
    int n = s.length();
    vector <int> p(n);
    p[0] = 0;
    for(int i = 1; i < n; i++) {
        int j = p[i - 1];
        while(j > 0 && s[i] != s[j]) {
            j = p[j - 1];
        }
        if(s[i] == s[j]) {
            j++;
        }
        p[i] = j;
    }
    vector <int> q(a.length());
    for(int i = 0; i < (int)a.length(); i++) {
        q[i] = p[i + (int)b.length() + 1];
    }
    return q;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string a, b;
    cin >> a >> b;
    int m = a.length();
    int n = b.length();
    vector<vector<int>> p(m, vector<int>(n));
    for(int i = 0; i < m; i++) {
        string temp;
        for(int j = i; j < m; j++) temp += a[j];
        p[i] = kmp(b, temp);
    }
    int ans = 0;
    pair <int, int> pos = {-1, -1};
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(p[i][j] > ans) {
                ans = p[i][j];
                pos = {i, j - p[i][j] + 1};
            }
            int x = p[i][j];
            if(x > 0 && i + x < m && j - x >= 0) {
                if(p[i + x][j - x] + p[i][j] > ans) {
                    ans = p[i + x][j - x] + p[i][j];
                    pos = {i, j - ans + 1};
                }
            }
        }
    }
    // repeat entire procedure after reversing a
    reverse(a.begin(), a.end());
    for(int i = 0; i < m; i++) {
        string temp;
        for(int j = i; j < m; j++) temp += a[j];
        // cout << temp << " ";
        p[i] = kmp(b, temp);
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(p[i][j] > ans) {
                ans = p[i][j];
                int ind = i + p[i][j] - 1;
                // cout << i << " " << j << ind << '\n';
                pos = {m - ind - 1, j - p[i][j] + 1};
            }
            int x = p[i][j];
            if(x > 0 && i + x < m && j - x >= 0) {
                if(p[i + x][j - x] + p[i][j] > ans) {
                    ans = p[i + x][j - x] + p[i][j];
                    int ind = i + x + p[i + x][j - x] - 1;
                    // cout << i << " " << j << ind << '\n';
                    pos = {m - ind - 1, j - ans + 1};
                }
            }
        }
    }
    cout << ans << '\n';
    cout << pos.first << " " << pos.second << '\n';
    
    return 0;
}

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40