暴力解法:
统计l,r中不同字符的数量。先用哈希数组存放 l ~ r
中的所有字符出现的次数,两个字符串字母出现次数之差除以二即为答案。
时间复杂度O(q*(r-l + 26)),最坏为O(n+26)*q),大约为 4*10^10。
正确解法:
使用前缀和来优化时间复杂度,用二维数组pre[N][26]
提前预处理,其中pre[i][j]
表示字符串的前i个字符中第j + 1
个小写字母出现的次数。
时间复杂度:O((n+q)*26)
,最坏为 1.04*10^7
代码:[submission:274145014]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, q;
int pre1[N][26], pre2[N][26];
string s1, s2;
void solve()
{
cin >> n >> q;
cin >> s1 >> s2;
memset(pre1, 0, sizeof pre1);
memset(pre2, 0, sizeof pre2);
for (int i = 0; i < n; i++) {
pre1[i + 1][s1[i] - 'a']++;
pre2[i + 1][s2[i] - 'a']++;
for (int j = 0; j < 26; j++) {
pre1[i + 1][j] += pre1[i][j];
pre2[i + 1][j] += pre2[i][j];
}
}
while (q--) {
int l, r;
cin >> l >> r;
int cnt = 0;
for (int i = 0; i < 26; i++) {
int cnt1 = pre1[r][i] - pre1[l - 1][i];
int cnt2 = pre2[r][i] - pre2[l - 1][i];
cnt += abs(cnt1 - cnt2);
}
cout << cnt / 2 << endl;
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}