Submission #1153589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153589		misavo	Necklace (Subtask 4) (BOI19_necklace4)	C++20	Compilation error	0 ms	0 KiB

necklace

// #include <bits/stdc++.h>
#include <iostream>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x <<  <<endl;
#define printp(a) for(auto x : a) cout << x.first <<  << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll t, n, m, k, a, b, tot;
string s1, s2;
ll lps[3009];

void solve() {
    cin >> s1 >> s2;

    f(i, 1, s1.size()) {
        ll len = lps[i-1];
        while (len && s1[len] != s1[i]) len = lps[len-1];
        if (len == 0) {f(j, 0, i) if (s1[i] == s1[j]) len = j + 1;}
        else if (s1[len] == s1[i]) len++;
        lps[i] = len;
    }

    // f(i, 0, s1.size()) cout << lps[i] << " ";
    // cout<<endl;

    vector<vll> chars(27, vll());
    f(i, 0, s1.size()) chars[s1[i] - 'a'].pb(i);

    ll ans = 0;
    f(i, 0, s2.size()) {
        if (chars[s2[i] - 'a'].empty()) continue;
        ll l = chars[s2[i] - 'a'].back();
        ll j = i, r = l;
        ll curr = 0;
        while (j < s2.size() && r < s1.size() && l >= 0) {
            if (s1[r] == s2[j]) {
                j++; r++;
            } else {
                if (!chars[s2[j] - 'a'].empty()) {
                    ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
                    if (back != -1) {
                        ll temp = chars[s2[j] - 'a'][back];
                        ll jj = j;
                        while (temp < l && jj < s2.size()) {
                            if (s1[temp] == s2[jj]) {
                                temp++; jj++;
                            } else {
                                if (!temp) break;
                                do {
                                    temp = lps[temp - 1];
                                } while (temp && s1[temp] != s2[jj]);
                            }
                        }
                        if (temp == l) ans = max(ans, jj - i);
                    } 
                }

                do {
                    r = lps[r - 1];
                } while (r && s1[r] != s2[j]);
                l = r - (j - i);
            }
        }
    }

    reverse(all(s2));
    f(i, 0, s2.size()) {
        if (chars[s2[i] - 'a'].empty()) continue;
        ll l = chars[s2[i] - 'a'].back();
        ll j = i, r = l;
        ll curr = 0;
        while (j < s2.size() && r < s1.size() && l >= 0) {
            if (s1[r] == s2[j]) {
                j++; r++;
            } else {
                if (!chars[s2[j] - 'a'].empty()) {
                    ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
                    if (back != -1) {
                        ll temp = chars[s2[j] - 'a'][back];
                        ll jj = j;
                        while (temp < l && jj < s2.size()) {
                            if (s1[temp] == s2[jj]) {
                                temp++; jj++;
                            } else {
                                if (!temp) break;
                                do {
                                    temp = lps[temp - 1];
                                } while (temp && s1[temp] != s2[jj]);
                            }
                        }
                        if (temp == l) ans = max(ans, jj - i);
                    } 
                }

                do {
                    r = lps[r - 1];
                } while (r && s1[r] != s2[j]);
                l = r - (j - i);
            }
        }
    }
    cout << ans <<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    t = 1;
    while (t--) {
        solve();
    }
}

Compilation message (stderr)

necklace.cpp: In function 'void solve()':
necklace.cpp:10:13: error: 'vector' was not declared in this scope
   10 | #define vll vector<long long>
      |             ^~~~~~
necklace.cpp:48:12: note: in expansion of macro 'vll'
   48 |     vector<vll> chars(27, vll());
      |            ^~~
necklace.cpp:3:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    2 | #include <iostream>
  +++ |+#include <vector>
    3 | 
necklace.cpp:10:20: error: expected primary-expression before 'long'
   10 | #define vll vector<long long>
      |                    ^~~~
necklace.cpp:48:12: note: in expansion of macro 'vll'
   48 |     vector<vll> chars(27, vll());
      |            ^~~
necklace.cpp:49:24: error: 'chars' was not declared in this scope; did you mean 'char'?
   49 |     f(i, 0, s1.size()) chars[s1[i] - 'a'].pb(i);
      |                        ^~~~~
      |                        char
necklace.cpp:53:13: error: 'chars' was not declared in this scope; did you mean 'char'?
   53 |         if (chars[s2[i] - 'a'].empty()) continue;
      |             ^~~~~
      |             char
necklace.cpp:54:16: error: 'chars' was not declared in this scope; did you mean 'char'?
   54 |         ll l = chars[s2[i] - 'a'].back();
      |                ^~~~~
      |                char
necklace.cpp:90:13: error: 'chars' was not declared in this scope; did you mean 'char'?
   90 |         if (chars[s2[i] - 'a'].empty()) continue;
      |             ^~~~~
      |             char
necklace.cpp:91:16: error: 'chars' was not declared in this scope; did you mean 'char'?
   91 |         ll l = chars[s2[i] - 'a'].back();
      |                ^~~~~
      |                char