【蓝桥备赛】字串简写

字串简写

数据范围 字符串的长度为5*10的五次方，on方时间复杂度会很大。

才用动态规划的思想，dp[i]以i开头的的可能性，因为长度必须大于等于k，当i小于k的时候，如果等于第一个字符，s1时，dp[i]=dp[i-1]+1,如果不等于dp[i]=dp[i-1]；

当i大于k-1时，如果以第二个字符结尾的，ans就需要加上dp[i-k+1]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll dp[N];
int main()
{int k;cin >> k;string s;cin >> s;char s1, s2;cin >> s1 >> s2;int res = 0;for (int i = 1; i < k; i++){dp[i] = dp[i - 1] + (s[i] == s1 ? 1 : 0);}for (int i = k; i < s.length(); i++){dp[i] = dp[i - 1] + (s[i] == s1 ? 1 : 0);if (s[i] == s2){res += dp[i - k];}}cout << res;
}