↵
↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
↵
#include <ext/pb_ds/assoc_container.hpp>↵
↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
#include <functional>↵
↵
#include <bits/stdc++.h>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
typedef long long ll;↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
ll t;↵
cin >> t;↵
while (t--) {↵
ll n, k;↵
cin >> n >> k;↵
string a, b;↵
cin >> a >> b;↵
vector < ll > mp(26, 0), mp1(26, 0);↵
vector < vector < ll >> calc(26, vector < ll > (n + 1, 0));↵
vector < ll > pre(n + 1, 0);↵
ll len = 0;↵
ll ans = 0;↵
if (a[0] == b[0]) {↵
pre[0] = 1;↵
len++;↵
}↵
calc[a[0] — 'a'][0] = 1;↵
mp1[a[0] — 'a']++;↵
for (ll i = 1; i < n; i++) {↵
calc[a[i] — 'a'][i]++;↵
if (a[i] == b[i]) {↵
len++;↵
pre[i] += (len + pre[i — 1]);↵
} else if (a[i] != b[i]) {↵
pre[i] = pre[i — 1];↵
len = 0;↵
}↵
}↵
for (ll i = 0; i < 26; i++) {↵
for (ll j = 1; j < n; j++) {↵
calc[i][j] += calc[i][j — 1];↵
}↵
}↵
if (k == 0) {↵
cout << pre[n — 1] << endl;↵
continue;↵
}↵
ll i = 0;↵
ll j = 0;↵
set < char > s1;↵
len = 0;↵
↵
ll count = 0;↵
while (j < n) {↵
mp[a[j] - 'a'] = j;↵
if (a[j] != b[j]) {↵
s1.insert(a[j]);↵
}↵
ll now = s1.size();↵
if (now > k) {↵
while (a[i] == b[i]) {↵
i++;↵
}↵
s1.erase(a[i]);↵
i = mp[a[i] - 'a'] + 1;↵
now--;↵
}↵
len = j - i + 1;↵
if (i == 0) {↵
ll count = 0;↵
for (auto x: s1) {↵
count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j]);↵
}↵
ans = max(ans, pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);↵
} else {↵
ll count = 0;↵
for (auto x: s1) {↵
count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j] + calc[x - 'a'][i - 1]);↵
}↵
ans = max(ans, pre[i - 1] + pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);↵
}↵
j++;↵
}↵
cout << ans << endl;↵
}↵
}↵
</spoiler>
↵
<spoiler summary="Spoiler">↵
...↵
</spoiler>↵
↵
#include <ext/pb_ds/assoc_container.hpp>↵
↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
#include <functional>↵
↵
#include <bits/stdc++.h>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
typedef long long ll;↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
ll t;↵
cin >> t;↵
while (t--) {↵
ll n, k;↵
cin >> n >> k;↵
string a, b;↵
cin >> a >> b;↵
vector < ll > mp(26, 0), mp1(26, 0);↵
vector < vector < ll >> calc(26, vector < ll > (n + 1, 0));↵
vector < ll > pre(n + 1, 0);↵
ll len = 0;↵
ll ans = 0;↵
if (a[0] == b[0]) {↵
pre[0] = 1;↵
len++;↵
}↵
calc[a[0] — 'a'][0] = 1;↵
mp1[a[0] — 'a']++;↵
for (ll i = 1; i < n; i++) {↵
calc[a[i] — 'a'][i]++;↵
if (a[i] == b[i]) {↵
len++;↵
pre[i] += (len + pre[i — 1]);↵
} else if (a[i] != b[i]) {↵
pre[i] = pre[i — 1];↵
len = 0;↵
}↵
}↵
for (ll i = 0; i < 26; i++) {↵
for (ll j = 1; j < n; j++) {↵
calc[i][j] += calc[i][j — 1];↵
}↵
}↵
if (k == 0) {↵
cout << pre[n — 1] << endl;↵
continue;↵
}↵
ll i = 0;↵
ll j = 0;↵
set < char > s1;↵
len = 0;↵
↵
ll count = 0;↵
while (j < n) {↵
mp[a[j] - 'a'] = j;↵
if (a[j] != b[j]) {↵
s1.insert(a[j]);↵
}↵
ll now = s1.size();↵
if (now > k) {↵
while (a[i] == b[i]) {↵
i++;↵
}↵
s1.erase(a[i]);↵
i = mp[a[i] - 'a'] + 1;↵
now--;↵
}↵
len = j - i + 1;↵
if (i == 0) {↵
ll count = 0;↵
for (auto x: s1) {↵
count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j]);↵
}↵
ans = max(ans, pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);↵
} else {↵
ll count = 0;↵
for (auto x: s1) {↵
count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j] + calc[x - 'a'][i - 1]);↵
}↵
ans = max(ans, pre[i - 1] + pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);↵
}↵
j++;↵
}↵
cout << ans << endl;↵
}↵
}↵
</spoiler>
