题意：
对于一个字符串S，一次操作你可以将左边第一个或者第二个字符删除，可以进行无限次操作。
给定n个字符串S(1),S(2)…S(n)， 问有多少个有序数对(i,j)，S(i)和S(j)其中一个串通过操作可以得到另外一个。
数据范围：n<=2e5，
∑
\sum
∑|S(i)|<=1e6，所有串互不相同且只由[a,z]组成
解法：
假设串的下标从1开始， 串S通过操作能获得的字符串一定是S的某个真后缀suf[pos]，左边再加上[1,pos-1]中的某个字符。
先将所有串倒着插入字典树， 对于每个串T，找能得到它的串S： T[2,n]一定是S的真后缀S[pos,m]，同时S[1,pos-1]还出现过T[1]， 令d(x,k)表示字典树以x为根的子树中，还出现过k的字符串结尾个数，可以用树形dp预处理， 那么统计答案就很简单了。 (预处理的细节还蛮多的)
最后要减掉n，因为每个串会匹配到自己。
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define PI pair<int,int>
const int maxm
=1e6+5;
string s
[maxm
];
int ans
;
int n
;
struct Trie
{
int a
[maxm
][26],tot
;
int type
[maxm
];
int val
[maxm
];
int ed
[maxm
][26];
void add(string s
){
int len
=s
.size();
int node
=0;
for(int i
=len
-1;i
>=0;i
--){
int v
=s
[i
]-'a';
if(!a
[node
][v
]){
a
[node
][v
]=++tot
;
type
[tot
]=v
;
}
node
=a
[node
][v
];
}
val
[node
]++;
}
void dfs(int x
){
for(int i
=0;i
<26;i
++){
int v
=a
[x
][i
];
if(!v
)continue;
dfs(v
);
val
[x
]+=val
[v
];
for(int j
=0;j
<26;j
++){
ed
[x
][j
]+=ed
[v
][j
];
}
}
ed
[x
][type
[x
]]=val
[x
];
}
void cal(string s
){
int len
=s
.size();
int node
=0;
for(int i
=len
-1;i
>=1;i
--){
int v
=s
[i
]-'a';
node
=a
[node
][v
];
}
for(int i
=0;i
<26;i
++){
int v
=a
[node
][i
];
if(!v
)continue;
ans
+=ed
[v
][s
[0]-'a'];
}
}
}T
;
signed main(){
cin
>>n
;
for(int i
=1;i
<=n
;i
++){
cin
>>s
[i
];
T
.add(s
[i
]);
}
T
.dfs(0);
for(int i
=1;i
<=n
;i
++){
T
.cal(s
[i
]);
}
ans
-=n
;
cout
<<ans
<<endl
;
return 0;
}
