题目描述
给定两个仅由小写英文字母组成的字符串 ( S ) 和 ( T )。
请你求出字符串 ( S ) 的所有非空子串中，不包含 ( T ) 作为其子序列的子串的数量。
输入格式
第一行输入字符串 ( S )
第二行输入字符串 ( T )
输出格式
输出一个整数，表示满足条件的非空子串数量。
数据范围
- ( 1 \leq |S| \leq 2 \times 10^5 )（( |S| ) 表示字符串 ( S ) 的长度）
- ( 1 \leq |T| \leq 50 )（( |T| ) 表示字符串 ( T ) 的长度）
- ( S ) 和 ( T ) 仅由小写英文字母组成
样例输入1
abc
ab
样例输出1
5
样例解释
( S=abc ) 的所有非空子串共6个：a、b、c、ab、bc、abc
其中包含 ab 作为子序列的只有 ab、abc 这2个
因此不满足条件的数量为 ( 6-1=5 )
题解
- 要求：统计满足条件的字串个数，在
S的所有非空子串s中，统计那些不包含T（子序列） 的个数。 - 问题转化为：以 \(l\) 为左边界，包含子序列
T的最小右边界为 \(r\) ,区间 \([l,r)\) 必然不包含子序列T，满足条件的子串个数为 \(r-l\)
3.问题转化为求 \(r\)的问题。 预处理 数组\(nxt[i][ch]\): 位置 \(i\)之后，字母 \(ch\)的位置。实现ch的匹配问题
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 200005;
char s[MAXN], t[60];
int nxt[MAXN][30], w[30], pos[MAXN];int main() {scanf("%s",s+1);scanf("%s",t+1);int ls = strlen(s + 1);int lt = strlen(t + 1);// 初始化：字符不存在时，位置为ls+1（越界标记）for (int i=1;i<=26;i++) w[i]=ls+1;for (int i=ls;i>=0;i--) {for (int j=1;j<=26;j++) nxt[i][j]=w[j];w[s[i]-'a'+1]=i; // 仅更新有效字符的位置}// 计算每个左端点 i 的最小右端点pos[i]for (int i=0;i<ls;i++) {int j=i;for (int k=1;j<=ls && k<=lt;k++) {j = nxt[j][ t[k] - 'a' + 1 ];}pos[i+1]=j;}// 统计long long Ans=0;for (int i=1;i<=ls;i++) Ans += pos[i] - i;cout<<Ans<<endl;return 0;
}