Submission #45793179

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/string>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define reb(i,n) for (int i = (int)(n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
using namespace std;
using ll = long long;
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

int main(){
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> len(n);
    string con = "";
    rep(i,n){
        string s; cin >> s;
        con += s + '?';
        len[i] = s.size();
    }
    auto sa = atcoder::suffix_array(con);
    auto lcp = atcoder::lcp_array(con,sa);
    int siz = con.size();
    vector<int> inv(siz);
    rep(i,siz) inv[sa[i]] = i;
    vector<int> a(siz), b(siz);
    for (int id = 0, i = 0; i < n; i++){
        for (int j = 0; j < len[i]+1; j++, id++){
            a[inv[id]] = i;
            b[inv[id]] = len[i] - j;
        }
    }
    rep(i,siz-1){
        chmin(lcp[i],min(b[i],b[i+1]));
    }
    ll ans = 0;
    for (int l = 0, r = 0; l < siz; l = r){
        while (r < siz && a[r] == a[l]) r++;
        vector<int> sub(r-l+1,0);
        rep(i,r-l+1){
            if (0 <= l-1+i && l-1+i < siz-1) sub[i] = lcp[l-1+i];
        }
        vector<int> lui = sub, rui = sub;
        rep(i,r-l) chmin(lui[i+1],lui[i]);
        reb(i,r-l) chmin(rui[i],rui[i+1]);
        rep(i,r-l){
            int ng = max(lui[i],rui[i+1]);
            if (i > 0) chmax(ng,lcp[l-1+i]);
            ans += max(b[l+i]-ng,0);
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result