记 \(S=\sum|s|\)。
枚举题目计数 \((i,j)\) 二元组中的 \(j\)。
考虑 \(s_i\) 能够匹配上 \(s_j\) 的条件，即不存在 \(s_j:[l,r]=s_i\) 且 \(s_j:[l',r']=s_k\)，\(l'\le l\)，\(r\le r'\)，\(k\ne i\ne j\)。
但这个存在被别的串包含的限制条件不好计数。
对匹配上 \(s_j\) 的所有子串考虑。量级为 \(O(n|s_j|)\) 的。
若存在 \(s_j:[l,r]=s_i\)，\(s_j:[l',r]=s_k\)，\(l'\le l\)。则 \(s_i\) 必定无用，因为该子串已经被 \(s_k\) 包含。类似支配对的感觉。
则每个位置只用枚举匹配右端点保留其能匹配上的串中的最长串。匹配子串量级降到 \(O(|s_j|)\)。
至于这个最长串怎么找。建立 ACAM，考虑 \(s_j:[1,x]\) 走到 fail 树上的 \(u\) 点，则等价于找到祖先中深度最深、作为其他串结尾的点代表的串即可。这个容易建树时 dfs \(O(S)\) 推出。预处理后能 \(O(S)\) 求得所有位置对应的最长串。
\(s_i\) 匹配上 \(s_j\) 的条件为，出现次数 \(=\) 不被其他匹配串包含的出现次数。
前者容易得出，对 \(s_j\) 在 fail 树上所有的点单点加 \(1\)，则出现次数转化为最终节点的子树和。复杂度 \(O(S\log S)\)。
考虑后者，实际上有了上面说的也是容易的，已经去掉了分别匹配到 \(s_j\) 的 \([l,r]\)，\([l',r']\)，\(r'=r,l'<r\) 的情况。用每个右端点匹配到的最长串容易去掉 \([l,r]\)，\([l',r']\)，\(r'>r,l'\le l\) 的情况。复杂度 \(O(S)\)。
总复杂度 \(O(S\log S)\)。
Takanashi Rikka
// Problem: CF1483F Exam
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1483F
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
#define int ll
const int N=1e6+5;
int t[N][26],f[N],lst[N],tot=1,w[N],ed[N],siz[N],dfn[N],ct;
vector<int>e[N];
string s[N];
int add(string s,int id){int u=1;for(int i=0,p;i<s.size();u=t[u][p],i++)if(!t[u][p=s[i]-'a'])t[u][p]=++tot,lst[tot]=u;return w[u]=id,u;
}
void build(){queue<int>dl;for(int i=0;i<26;i++)(t[1][i]?(dl.push(t[1][i]),f[t[1][i]]):t[1][i])=1;while(!dl.empty()){int u=dl.front();dl.pop();for(int i=0;i<26;i++)(t[u][i]?(dl.push(t[u][i]),f[t[u][i]]):t[u][i])=t[f[u]][i];}for(int i=2;i<=tot;i++)e[f[i]].pb(i);
}
void dfs(int u,int fa){dfn[u]=++ct;siz[u]=1;if(!w[u])w[u]=w[fa];for(int v:e[u])dfs(v,u),siz[u]+=siz[v];
}
int tr[N],c[N],l[N];
void upd(int x,int d){for(;x<=ct;x+=lowbit(x))tr[x]+=d;}
int ask(int x){int res=0;for(;x;x-=lowbit(x))res+=tr[x];return res;}
void UesugiErii(){int n,ans=0;cin>>n;for(int i=1;i<=n;i++)cin>>s[i],ed[i]=add(s[i],i);build();dfs(1,0);for(int i=1;i<=n;i++){vector<int>q;for(int u=ed[i];u!=1;u=lst[u])upd(dfn[u],1);for(int j=0,u=1,p,tmp;j<s[i].size();j++){u=t[u][p=s[i][j]-'a'];tmp=(j==s[i].size()-1?w[f[u]]:w[u]);l[j]=0;if(tmp)l[j]=tmp;}int r=s[i].size();for(int j=s[i].size()-1,tmp;~j;j--)if(l[j])((tmp=j-s[l[j]].size()+1)>=r?0:(q.pb(l[j]),++c[l[j]],r=tmp));for(int u:q){int i=ed[u];if(c[u]==ask(dfn[i]+siz[i]-1)-ask(dfn[i]-1))++ans;c[u]=0;}for(int u=ed[i];u!=1;u=lst[u])upd(dfn[u],-1);}cout<<ans;
}
signed main(){//cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}