Submission #348285

#	Time	Username	Problem	Language	Result	Execution time	Memory
348285		elizarv	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	279 ms	620 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T a,Args... args) {cout<<a<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

vector<int> prefix_function(string &s) {
    int n = s.size();
    vector<int> pf(n);
    pf[0] = 0;
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) j = pf[j-1];
        if (s[i] == s[j]) j++;
        pf[i] = j;
    }
    return pf;
}

vector<int> kmp(string &s, string &p) {
    int n = s.size(), m = p.size(), cnt = 0;
    vector<int> mx(n, 0);
    if(!m)return mx;
    vector<int> pf = prefix_function(p);
    for(int i = 0, j = 0; i < n; i++) {
        while(j && s[i] != p[j]) j = pf[j-1];
        if(s[i] == p[j]) j++;
        mx[i] = j;
        if(j == m) {
            cnt++;
            j = pf[j-1];
        }
    }
    return mx;
}

int ans, a, b;

void go(string &s, string &t, bool f = false){
    int n = s.size();
    int m = t.size();
    string rev = t;
    reverse(rev.begin(), rev.end());
    forn(i, 0, n+1){
        string lf = s.substr(0, i);
        string rg = s.substr(i, n-i);
        reverse(lf.begin(), lf.end());
        vector<int> suf = kmp(rev, lf);
        vector<int> pref = kmp(t, rg);
        reverse(suf.begin(), suf.end());
        forn(j, 0, m){
            int mchb = pref[j], mcha = 0;
            if(j + 1 < m) mcha = suf[j + 1];
            int aux = mcha + mchb;
            if(mchb) mchb--;
            if(mcha) mcha--;
            if(aux > ans){
                ans = aux;
                a = i - mcha - 1;
                b = j - mchb;
                if(f){
                    a = n - a - aux;
                }
            }

        }
    }
}


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

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

   go(s, t);
   reverse(s.begin(), s.end());
   go(s, t, true);
   cout << ans << endl;
   cout << a << " " << b << endl;



 }

• Subtask 1: 15 / 15