Submission #61443294

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long;
using ull = unsigned long long;

int prefix_counter(string &s,string &t){
    int m = t.size();
    int idx = 0;
    int count = 0;
    for(char c : s){
        if(c==t[idx]){
            idx++;
            count++;
        }
        if(idx>=m) {
            return count;
        }
    }
    return count;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string t;
    cin >> n >> t;
    string revt = t;
    ranges::reverse(revt);
    vector<string> s(n);
    for(int i=0;i<n;++i)cin>>s[i];
    vector<vector<int>> ps_count(2,vector<int>(n));;
    for(int i=0;i<n;++i){
        ps_count[0][i] = prefix_counter(s[i],t);
        ranges::reverse(s[i]);
        ps_count[1][i] = prefix_counter(s[i],revt);
    }

    ranges::sort(ps_count[0]);
    ranges::sort(ps_count[1]);

    ll ans = 0;

    /*
    const auto &it = ps_count[1];
    for(int i=0;i<n;++i){
        int target = (int)t.size() - ps_count[0][i];
        ans += end(it) - lower_bound(begin(it),end(it),target);
    }
    */

    int r=n-1;
    for(int i=0;i<n;++i){
        int req = (int)t.size() - ps_count[0][i];
        while(r>=0 && ps_count[1][r] >= req){
            --r;
        }
        ans += n-r-1;
    }

    cout << ans << endl;
}

Submission Info

Judge Result