From 14e41732ebea0d1f473e49193fc710dd5c3c73c0 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Mon, 22 May 2023 13:00:42 +0300 Subject: [DAAP/H3] Added somewhat working solution 30/100 points --- .../Practicum/Homeworks/HW3-Strings.cpp | 75 ++++++++++++++++++++++ 1 file changed, 75 insertions(+) create mode 100644 Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp diff --git a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp new file mode 100644 index 0000000..1d26d1d --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW3-Strings.cpp @@ -0,0 +1,75 @@ +#include +using namespace std; + +typedef pair Query; + +char S[2000005] = { '\0' }; +long long QN = 0; +Query qs[2000005] = {{0,0}}; +long long mem[2000005] = { 0 }; + +char* lastLeftMatching(char* c) { + char* l = c; + while (l != S && *(l-1) == *c) { + l--; + } + return l; +} + +char* lastRightMatching(char* c) { + char* r = c; + while (*(r+1) == *c) { + r++; + } + return r; +} + +int main() { + ios::sync_with_stdio(false); + cin.tie(NULL); + cout.tie(NULL); + + cin.getline(S, 2000005); + cin >> QN; + for (long long i = 0; i < QN; i++) { + Query qi = {0,0}; + cin >> qi.first >> qi.second; + qs[i] = qi; + } + + for (Query& q : qs) { + if (q.first == 2) { + char* l = lastLeftMatching(S + q.second), *r = lastRightMatching(S + q.second); + // cout << "Del " << r-l+1 << endl; + long long nl = (S + q.second) - l; + while (l <= S + q.second) { + mem[l-S] = nl; + l++; + } + nl = r - (S + q.second); + while (l <= r) { + mem[l-S] = nl; + l++; + } + S[q.second] = '#'; + } + else if (q.first == 1) { + if (mem[q.second] > 0) { + // cout << "From memory "; + cout << mem[q.second] << endl; + continue; + } + // cout << S << endl; + char* l = lastLeftMatching(S + q.second), *r = lastRightMatching(S + q.second); + long long len = r-l+1; + cout << len << endl; + while (l <= r) { + mem[q.second] = len; + l++; + } + } + else { + break; + } + } +} -- cgit v1.3.1-26-gb76a