#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
#include<list>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<ctime>
#include<random>
#include<functional>
#include<iostream>
#include<istream>
#include<streambuf>
#include<fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
const ll MAXN=5e5+10;
int n;
string tt;
int pre[MAXN];
int suf[MAXN];
inline int match(string s,string t){
int ind=0;
for(int i=0;i<(int)s.size();i++){
if(ind<(int)t.size()&&s[i]==t[ind]){
ind++;
}
}
return ind;
}
inline int match2(string s,string t){
int ind=t.size()-1;
int cnt=0;
for(int i=s.size()-1;i>=0;i--){
if(ind>=0&&s[i]==t[ind]){
ind--;
cnt++;
}
}
return cnt;
}
ll ans;
void solve(){
cin>>n;
cin>>tt;
for(int i=1;i<=n;i++){
string s;
cin>>s;
pre[i]=match(s,tt);
suf[i]=match2(s,tt);
suf[i]=tt.size()-suf[i];
}
sort(suf+1,suf+n+1);
sort(pre+1,pre+n+1);
int ind=n;
for(int i=n;i>=1;i--){
while(ind&&pre[i]<suf[ind]){
ind--;
}
ans+=ind;
}
cout<<ans<<endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
int T=1;
while(T--){
solve();
}
return 0;
}
我这样写,把求前缀和后缀写成函数,然后Atcoder上T了3个点
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
#include<list>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<ctime>
#include<random>
#include<functional>
#include<iostream>
#include<istream>
#include<streambuf>
#include<fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
const ll MAXN=5e5+10;
int n;
string t;
int pre[MAXN];
int suf[MAXN];
inline int match2(string s,string t){
int ind=t.size()-1;
int cnt=0;
for(int i=s.size()-1;i>=0;i--){
if(ind>=0&&s[i]==t[ind]){
ind--;
cnt++;
}
}
return cnt;
}
ll ans;
void solve(){
cin>>n;
cin>>t;
for(int i=1;i<=n;i++){
string s;
cin>>s;
int ind=0;
for(int i=0;i<(int)s.size();i++){
if(ind<(int)t.size()&&s[i]==t[ind]){
ind++;
}
}
pre[i]=ind;
ind=t.size()-1;
int cnt=0;
for(int i=s.size()-1;i>=0;i--){
if(ind>=0&&s[i]==t[ind]){
ind--;
cnt++;
}
}
suf[i]=t.size()-cnt;
}
sort(suf+1,suf+n+1);
sort(pre+1,pre+n+1);
int ind=n;
for(int i=n;i>=1;i--){
while(ind&&pre[i]<suf[ind]){
ind--;
}
ans+=ind;
}
cout<<ans<<endl;
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(NULL));
int T=1;
while(T--){
solve();
}
return 0;
}
但这样写就A了,是函数调用时间的问题吗,求助各位大佬