预处理出 数组,表示对于位置 而言,下一个字母 位置在哪。()
这样对于字符串 来说,只要它的某一个字母和 的第一个字母相同,我们就可以用 数组快速找到最短的一个包含 的子串。
那么如何不重不漏地统计数量呢?假设我们找到了一个最短的包含 的子串,这个子串的起点和终点为 ,如果我们直接写出 肯定会重复统计,例如 中有多个不相交的子串且包含 的子串。
我们可以记录上一次包含 的子串起点,从那个点出发开始选择子串,这样保证每次计算子串数量的时候起点都是递增的,自然就不会有重复了。
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 3e5 + 5;
int auto_chicken[maxn][27], last[27];
int main(){
string s, t;
cin >> s >> t;
memset(last, -1, sizeof last);
for(int i = s.size() - 1; i >= 0; i--){
for(int j = 0; j <= 25; j++){
auto_chicken[i][j] = last[j];
}
last[s[i] - 'a'] = i;
}
int last_ans = -1;
long long ans = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] != t[0]) continue;
int now = i, flag = 0;
if(t.size() == 1){
ans += 1ll * (i - last_ans) * (s.size() - i);
continue;
}
for(int j = 1; j < t.size(); j++){
if(auto_chicken[now][t[j] - 'a'] != -1){
now = auto_chicken[now][t[j] - 'a'];
}else{
break;
}
if(j == t.size() - 1 && now != -1){
ans += 1ll * (i - last_ans) * (((int)s.size()) - now);
last_ans = i;
}
}
}
cout << ans << endl;
}