以下 \(\Sigma\) 为字符集。
首先单次询问 \(O(|\Sigma||S|)\) 的暴力是显然的：建出 trie 树，然后每次把对应的字符串在上边扫，加上对应位置比它小的子树的大小。
然后接下来有两种方法。
正解
首先在线大概是没什么前途的，考虑离线，建出 trie 树之后在上边 dfs，处理挂在每个节点上的询问。具体的，我们记录每个字符串在 trie 上的结尾位置，把询问挂在上边。
考虑 \(s\) 字典序比 \(t\) 更小的条件：要么 \(s\) 是 \(t\) 的前缀，要么 \(s\) 和 \(t\) 在第一位出现不同的位置 \(i\) 满足 \(s_i<t_i\)。第一种可以在每个串的结尾打标记，dfs 的时候扫到一个点就加上。考虑第二种。
题解给出了这样一种做法：对 \(|\Sigma|^2\) 种不同的字符大小关系分别计算贡献，然后加起来。我们可以记录一个 \(val_{i,j}\) 表示字符 \(i\) 比字符 \(j\) 大时的贡献，那么对于每个询问我们可以 \(O(|\Sigma|^2)\) 地扫每一对字符累加 \(val\)。\(val\) 的更新是简单的，dfs 时搜一个儿子 \(i\)，那么对于所有兄弟 \(j\)，把当前的 \(val_{i,j}\) 加上 \(j\) 子树的大小。
总复杂度 \(O((n+q)|\Sigma|^2)\)。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m,num,trie[400010][26],sz[400010],cnt[400010],id[100010];
string s[100010];
void ins(string s,int x){
int p=0;
for(int i=0;i<s.length();i++){
if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++num;
p=trie[p][s[i]-'a'];sz[p]++;
}
cnt[p]++;id[x]=p;
}
int sum,ans[100010],tmp[26],val[26][26];
vector<pair<string,int> >q[400010];
void dfs(int x){
sum+=cnt[x];
for(pair<string,int>p:q[x]){
for(int i=0;i<26;i++)tmp[p.first[i]-'a']=i;
ans[p.second]=sum;
for(int i=0;i<26;i++){
for(int j=i+1;j<26;j++){
if(tmp[i]<tmp[j])ans[p.second]+=val[j][i];
else ans[p.second]+=val[i][j];
}
}
}
for(int i=0;i<26;i++){
if(!trie[x][i])continue;
for(int j=0;j<26;j++){
if(i==j)continue;
if(trie[x][j])val[i][j]+=sz[trie[x][j]];
}
dfs(trie[x][i]);
for(int j=0;j<26;j++){
if(i==j)continue;
if(trie[x][j])val[i][j]-=sz[trie[x][j]];
}
}
sum-=cnt[x];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];ins(s[i],i);
}
cin>>m;
for(int i=1;i<=m;i++){
int od;cin>>od>>s[0];
q[id[od]].push_back(make_pair(s[0],i));
}
dfs(0);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
暴力
感觉这个暴力比正解更具有启发性（
我们仍然建出 trie 树。然后仿照后缀树，我们把 trie 压缩一下。我们把不是一个串的结尾且只有一个儿子的节点去掉，那么剩下的点要么是一个串的终点，要么不止一个儿子。容易证明这时 trie 的树高是 \(O(\sqrt{|S|})\) 的，因为最多有 \(O(\sqrt{|S|})\) 种不同的长度。于是我们在压缩 trie 上跑暴力就能过了。
复杂度 \(O(|\Sigma|(|S|+q\sqrt{|S|}))\)。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m,num,trie[400010][26],sz[400010],len[400010],cnt[400010];
string s[100010];
void ins(string s,int x){
int p=0;
for(int i=0;i<s.length();i++){
if(!trie[p][s[i]-'a'])trie[p][s[i]-'a']=++num;
p=trie[p][s[i]-'a'];sz[p]++;
}
cnt[p]++;
}
void dfs(int x){
int son=0,tmp=0;len[x]=1;
for(int i=0;i<26;i++){
if(trie[x][i]){
tmp++,son=trie[x][i];dfs(trie[x][i]);
}
}
if(tmp==1&&!cnt[x]){
for(int i=0;i<26;i++)trie[x][i]=trie[son][i];
len[x]=len[son]+1;cnt[x]+=cnt[son];
}
}
int query(string s,string tmp){
int p=0,ans=cnt[0];
for(int i=len[0]-1;i<s.length();i+=len[p],ans+=cnt[p]){
for(int j=0;j<26;j++){
if(tmp[j]==s[i])break;
if(trie[p][tmp[j]-'a'])ans+=sz[trie[p][tmp[j]-'a']];
}
p=trie[p][s[i]-'a'];
}
return ans;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];ins(s[i],i);
}
dfs(0);
cin>>m;
while(m--){
int id;string tmp;cin>>id>>tmp;
cout<<query(s[id],tmp)<<'\n';
}
return 0;
}