AT_abc452_d [ABC452D] No-Subsequence Substring

题目描述

给定由小写英文字母组成的字符串 S 和 T。

求 S 的所有非空子串中，不包含 T 作为（不一定连续的）子序列的子串个数。

这里，S 的两个子串只要取出的位置不同，即使字符串内容相同也视为不同子串。

子串：字符串 X 的子串是指从 X 开头删除 0 个以上字符、从末尾删除 0 个以上字符后得到的字符串。

子序列：字符串 X 的子序列是指从 X 中删除 0 个以上元素后，剩余元素按原顺序排列得到的字符串。

输入格式

输入从标准输入以以下格式给出：

S T

输出格式

一行，输出答案。

输入输出样例 #1

输入 #1

abrakadabra
aba

输出 #1

51

输入输出样例 #2

输入 #2

aaaaa
a

输出 #2

0

输入输出样例 #3

输入 #3

rdddrdtdcdrrdcredctdordoeecrotet
dcre

输出 #3

263

说明/提示

样例解释 1

例如，S 的第 1 个字符到第 3 个字符组成的子串 abr 不包含 T 作为子序列。此外，k（仅 S 的第 5 个字符）和 akada（S 的第 4 个字符到第 8 个字符）等共 51 个子串满足条件。

注意：abr 既可以作为 S 的第 1 到 3 个字符的子串，也可以作为第 8 到 10 个字符的子串，但由于取出位置不同，它们被视为不同的子串进行计数。

样例解释 2

S 的所有非空子串都包含 T 作为子序列。因此没有满足条件的子串，输出 0。

数据范围

• S 由小写英文字母组成
• 记 |S| 为 S 的长度，满足$ 1 \le |S| \le 2 \times 10^5$
• T 由小写英文字母组成
• 记 |T| 为 T 的长度，满足$ 1 \le |T| \le 50$

代码

// Sunshine, sunshine, ladybugs awake!  
// Clap your hooves and do a little shake!  
#include <bits/stdc++.h>  
#define int long long  
#define endl '\n'  
using namespace std;  
  
using PII=pair<int,int> ;  
using PIC=pair<int,char> ;  
inline static constexpr int MAXN=200010;  
inline static constexpr int mod=676767677;  
  
void solve() {  
    string s,t;  
    cin>>s>>t;  
        int n=s.size(),m=t.size();  
        vector<array<int,26>> nxt(n+1);  
    nxt[n].fill(n);  
        for(int i=n-1;i>=0;i--){  
        nxt[i]=nxt[i+1];  
        nxt[i][s[i]-'a']=i;  
    }  
        int ans=0;  
    for(int L=0;L<n;L++){  
        int curr=L;  
        bool flag=true;  
                for(int j=0;j<m;j++){  
            if(curr==n){  
                flag=false;  
                break;  
            }  
                        curr=nxt[curr][t[j]-'a'];  
            if(curr==n){  
                flag=false;  
                break;  
            }  
            curr++;  
        }  
                if(flag){  
            ans+=(curr-1)-L;  
        }else{  
            ans+=n-L;  
        }  
    }  
    cout<<ans<<endl;  
}  
  
signed main() {     ios_base::sync_with_stdio(false);  
    cin.tie(NULL);  
    //int t;cin >> t;while (t--)         solve();  
    return 0;  
}