宁波广告公司网站建设,模板网站视频,网站设计评价指标,母婴网站源码dede一、题目描述
P8715 [蓝桥杯 2020 省 AB2] 子串分值
二、问题简析
记录字符串 s s s 的 第 i i i 个字符 s i s_i si#xff08; 0 ≤ i s . s i z e 0\leq is.size 0≤is.size#xff09;上一次出现的位置 p r e i pre_i prei、下一次出现的位置 n…一、题目描述
P8715 [蓝桥杯 2020 省 AB2] 子串分值
二、问题简析
记录字符串 s s s 的 第 i i i 个字符 s i s_i si 0 ≤ i s . s i z e 0\leq is.size 0≤is.size上一次出现的位置 p r e i pre_i prei、下一次出现的位置 n e x i nex_i nexi仅包含 s i s_i si 的字串个数为 ( i − ( p r e i 1 ) 1 ) ∗ ( n e x i − 1 − i 1 ) (i - (pre_i 1) 1) * (nex_i - 1 - i 1) (i−(prei1)1)∗(nexi−1−i1)即 ( i − p r e i ) ∗ ( n e x i − i ) (i-pre_i)*(nex_i-i) (i−prei)∗(nexi−i)。只需要遍历所有的 s i s_i si将所有字串个数相加就是所求。 p r e i pre_i prei因为字符串里只有 26 26 26 个小写字母所以创建一个容量为 26 26 26 的临时数组 rec[26]记录对应字母上次出现的下标rec[0] 对应 arec[1] 对应 b以此类推。
1、因为要记录上一次出现的位置所以要从左往右遍历并更新相应的 rec[i]。2、需要注意每个字母首次出现的 p r e i pre_i prei因为是首次出现所以下标从 0 0 0 至 i i i 的字母都可以是字串的开头即 p r e i 1 0 pre_i10 prei10。因此rec[26] 要初始化为 -1。 n e x i nex_i nexi与 p r e i pre_i prei 类似也需要一个临时数组 rec[26]。不同点
1、从右往左遍历并更新相应字母的下标2、rec[26] 初始化为 s.size因为每个字母最后一次出现时下标从 i i i 至 s . s i z e − 1 s.size-1 s.size−1 都可以作为字串的结尾即 n e x i − 1 s . s i z e − 1 nex_i-1s.size-1 nexi−1s.size−1。 三、AC代码
#include bits/stdc.husing namespace std;
typedef long long ll;const int MAX 1e5 3;
int pre[MAX], nex[MAX], rec[30];
string s;int main()
{#ifdef LOCALfreopen(test.in, r, stdin);#endifcin s;int sSize s.size();fill(rec, rec 26, -1);for (int i 0; i sSize; i){pre[i] rec[s[i] - a];rec[s[i] - a] i;}fill(rec, rec 26, sSize);for (int i sSize - 1; i 0; i--){nex[i] rec[s[i] - a];rec[s[i] - a] i;}ll ans 0;for (int i 0; i sSize; i){ans (i - pre[i]) * (nex[i] - i);}cout ans endl;return 0;
}完
