Submission #1259117

#TimeUsernameProblemLanguageResultExecution timeMemory
1259117newsboyNecklace (Subtask 4) (BOI19_necklace4)C++20
0 / 15
173 ms53360 KiB
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <iomanip> #include <set> #include <map> #include <numeric> #include <unordered_set> #include <unordered_map> #include <bitset> #include <climits> #include <queue> #include <deque> #include <stack> #include <cmath> #include <tuple> #include <cassert> #include <array> #include <list> #include <random> #include <initializer_list> #include <chrono> using namespace std; using i64 = long long; using u64 = unsigned long long; vector<int> prefixFunction(string& s) { vector<int> pi(s.size()); for (int i = 1; i < s.size(); i++) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) { j = pi[j - 1]; } if (s[i] == s[j]) { j++; } pi[i] = j; } return pi; } string s, t; void work(int& res, int& ls, int& lt, bool& o) { if (o) { reverse(s.begin(), s.end()); } int n = s.size(); int m = t.size(); string g = s + "?" + t; vector<vector<int>> pi(n); for (int i = 0; i < n; i++) { pi[i] = prefixFunction(g); g.erase(g.begin()); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int x = pi[i][n - i + 1 + j]; if (x > res) { res = x; ls = i; lt = j - x + 1; } if (i + x < n && n - (i + x) + 1 + (j - x) < pi[i].size()) { int y = pi[i + x][n - (i + x) + 1 + (j - x)]; if (x + y > res) { res = x + y; ls = (o ? n - (i + res - 1) - 1 : i); lt = (j - x) - y + 1; } } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> s >> t; bool o = 0; int res = 0; int ls = -1, lt = -1; work(res, ls, lt, o); o ^= 1; work(res, ls, lt, o); cout << res << '\n'; cout << ls << " " << lt << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...