题目大意
给你 \(n\) 个字符串 \(s\)，和一个字符串 \(t\)。
问你，有多少组是 \(s_j\) 拼在 \(s_i\) 后面所组成的新字符串中，\(t\) 是其子序列。
思路
分析：\(5 \times 10^5\) 的数据肯定需要 \(O(n)\) 或 \(O(n \log n)\) 的时间复杂度过掉，\(\log n\) 很容易想到应该是二分，于是我们就往二分的思路去想。
首先先进行预处理：
我们可以遍历 \(n\) 个 \(s\)。我们可以开两个数组：
- \(f\) 数组，\(f_i\) 记录的是每一个 \(s_i\) 的最长前缀
- \(b\) 数组，\(b_i\) 记录的是每一个 \(s_i\) 的最长后缀
当什么情况两个字符串拼起来的新字符串，\(t\) 可以是它们的子序列呢？
如果前面的字符串的最长前缀 \(+\) 后面的字符串的最长后缀的长度大于等于 \(t\) 的长度，那么我们就可以拼出一个子序列。
于是，我们可以枚举前面的字符串，然后二分出最长后缀大于等于 \(n\) 减去这个字符串的最长前缀的个数。那么就是这个字符串后面可以接着的字符串的个数，然后对答案 \(ans\) 加上这个数。
因此我们就完成这一题了。
最后的提醒：十年 OI 一场空，不开 long long 见祖宗
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
int n;
string t,s[N];
int f[N],b[N]; // 前缀和后缀数组
signed main(){
cin >> n >> t;
for(int i = 1 ;i <= n;i++)
cin >> s[i];
for(int i = 1;i <= n;i++){
for(int j = 0 ;j < s[i].size();j++)
if(s[i][j] == t[f[i]])
f[i]++;//计算si的最大前缀
for(int j = s[i].size()-1;j >= 0;j--)
if(s[i][j] == t[t.size()-1-b[i]])
b[i]++;//计算si的最大后缀
}
int m = t.size();
sort(f+1,f+1+n);sort(b+1,b+1+n);//排序以便二分
int ans=0;
for(int i = 1;i <= n;i++) ans+= n-(lower_bound(b+1,b+1+n,m-f[i])-b)+1;//进行二分的操作，计算以si为前面的字符串，后面有多少种可能
cout<<ans;
return 0;
}