[DAAP/H3] Added somewhat working solution

30/100 points

1 files changed, 75 insertions, 0 deletions

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 <iostream>
+using namespace std;
+
+typedef pair<long long, long long> 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;
+		}
+	}
+}