Submission #585272

#	Time	Username	Problem	Language	Result	Execution time	Memory
585272		ImtiazCho	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	1558 ms	5980 KiB

necklace

/** Bismillahir Rahmanir Rahim **/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define endl '\n'
#define fi first
#define se second
#define ull unsigned ll
#define lld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define Fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define debug(...) cerr << "[" << #__VA_ARGS__ << "] =>", dbg_out(__VA_ARGS__)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Up, typename... Down> void dbg_out(Up U, Down... D) { cerr << ' ' << U; dbg_out(D...); }

string s, t;
int ans = 0, l_idx,l_idx1;
vector<int> kmp(const string &a, const string &b) {
    // generating prefix function
    int m = sz(b);
    vector<int> pi(m);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && b[i] != b[j]) j = pi[j - 1];
        if (b[i] == b[j]) j++;
        pi[i] = j;
    }

    // genarating chk
    int n = sz(a);
    vector<int> chk(n, 0);
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && a[i] != b[j]) j = pi[j - 1];
        if (a[i] == b[j]) {
            j++;
            chk[i] = j;
            if (j == m) j = pi[j - 1];
        }
    }

    return chk;
}

void solve() {
    cin >> s >> t;

    string tr = t;
    reverse(all(tr));

    int turn = 2;
    int n = sz(s);
    int m = sz(t);

    while (turn--) {
        for (int i = 0; i < n; i++) {

            string left = s.substr(0, i);
            reverse(all(left));

            string right = s.substr(i, n - i);

            vector<int> chk = kmp(t, right);
            debug(t, right);
            vector<int> chk1 = kmp(tr, left);
            debug(tr, left);
            reverse(all(chk1));
            int cnt = 0;
            for (int j = 0; j < sz(chk1); j++) {
                if (chk1[j]) {
                    cnt++;
                    chk1[j] = cnt;
                    continue;
                } 
                cnt = 0;
            }

            int len = 0;
            for (int j = 0; j < m; j++) {
                int len_right = chk[j];
                int pos = j - len_right;
                int len_left = chk1[pos];
                debug(len_right, pos, len_left);
                if (len_right + len_left > ans) {
                    ans = len_right + len_left;
                    l_idx = (i - chk1[j]);
                    l_idx1 = (j - chk1[j]);
                }
            }

            for (int j = 0; j < m; j++) {
                int len_right = chk1[j];
                int pos = j - len_right;
                int len_left = chk[pos];

                if (len_right + len_left > ans) {
                    ans = len_right + len_left;
                    l_idx = (i - chk1[j]);
                    l_idx1 = (m - (j + 1));
                }
            }

        }


        swap(t, tr);
    }
    cout << ans << endl;
    cout << l_idx << " " << l_idx1 << endl;
}
int main()
{
   Fastio;
   int tt = 1; 
//    cin >> tt;
   while (tt--) solve();

   return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void solve()':
necklace.cpp:84:17: warning: unused variable 'len' [-Wunused-variable]
   84 |             int len = 0;
      |                 ^~~

• Subtask 1: 0 / 15