链接：https://ac.nowcoder.com/acm/problem/15160
来源：牛客网
题目描述
小H发现这些话非常相似，现在小H想知道，有多少对句子可能是相同的
注意：(x,x)这样的句子对不计入答案，(x,y)，(y,x)视为同一个句子对(详见样例)
输入描述:
第1行，一个整数N
第2~N+1行，每行一个字符串表示一句话
2≤N≤500,000，所有字符串的总长不超过1,000,000
输出描述:
一行，一个整数，表示你给出的答案
具体思路：
首先，这个题满足一个结论，假设我们当前要比较字符串A和字符串B是不是满足的，假设l1为字符串开头位置到第一个‘#’的前缀，s1为字符串倒序中到最后一个'#‘的后缀。
同理l2和s2.如果字符串A和字符串B是满足题目条件的，那么l1和l2中，肯定有一个是另外一个的前缀。s1和s2中，肯定有一个是另外一个的后缀。
然后知道这个结论之后，我们再去想如何去求答案。
首先我们需要建立两颗trie树，正序一颗，后序一颗。对于每一个字符串，我们保存当前前缀中第一个'#'之前的前一个坐标x1和当前后缀中最后一个'#'后面的第一个点的坐标x2，然后建图保存x1指向x2。
我们的思路是在正序trie树上跑每一个字符串的前缀（对于当前这个字符串的前缀是按照字典树跑的，肯定满足当前这个串是之前已经存储过的前缀的前缀），找到这个前缀的末尾节点所连向的后序trie树的节点v，当前这个人的贡献 就是 后序trie树上这个节点v的祖先节点中已经储存了多少人 + 这个节点所代表的子树中已经储存了多少人。正好对应了当前这个后缀是别人的后缀 以及 别人的后缀 是 当前这个后缀 的后缀 这两种情况。
对于具体的代码实现
对后序字典序跑一个dfs序，因为需要用到区间的信息。每一次查询的时候，对于当前 后序trie树上这个节点v的祖先节点中已经储存了多少人 这个信息，
我们可以开一个树状数组维护这个节点到根节点的人的个数。对于 这个节点所代表的子树中已经储存了多少人 这个信息，我们需要另外再开一个树状数组维护这个区间的信息（如果用一个的话会算重），这个区间对答案的贡献就是以当前节点所代表的的子树中有多少人。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 # define int ll 6 const int maxn = 3e6+100; 7 int tot_pre,tot_suf; 8 int ch_pre[maxn][30],ch_suf[maxn][30]; 9 vector<int>Edge[maxn]; 10 int add_ch_pre(char str[]){ 11 int len=strlen(str); 12 int p=0; 13 for(int i=0;i<len;i++){ 14 if(str[i]=='#')break; 15 int u=str[i]-'a'; 16 if(!ch_pre[p][u])ch_pre[p][u]=++tot_pre; 17 p=ch_pre[p][u]; 18 } 19 return p; 20 } 21 int add_ch_suf(char str[]){ 22 int len=strlen(str); 23 int p=0; 24 for(int i=len-1;i>=0;i--){ 25 if(str[i]=='#')break; 26 int u=str[i]-'a'; 27 if(!ch_suf[p][u])ch_suf[p][u]=++tot_suf; 28 p=ch_suf[p][u]; 29 } 30 return p; 31 } 32 int dfs_ord; 33 int L[maxn],R[maxn]; 34 void dfs(int u){ 35 L[u]=++dfs_ord; 36 for(int i=0;i<26;i++){ 37 if(!ch_suf[u][i])continue; 38 dfs(ch_suf[u][i]); 39 } 40 R[u]=dfs_ord; 41 } 42 int ans=0; 43 int tree1[maxn<<2],tree2[maxn<<2]; 44 int lowbit(int u){return u&-u;} 45 int sum_tree1(int pos){ 46 int sum=0; 47 while(pos){ 48 sum+=tree1[pos]; 49 pos-=lowbit(pos); 50 } 51 return sum; 52 } 53 int sum_tree2(int pos){ 54 int sum=0; 55 while(pos){ 56 sum+=tree2[pos]; 57 pos-=lowbit(pos); 58 } 59 return sum; 60 } 61 void add_tree1(int pos,int val){ 62 while(pos<=dfs_ord){ 63 tree1[pos]+=val; 64 pos+=lowbit(pos); 65 } 66 } 67 void add_tree2(int pos,int val){ 68 while(pos<=dfs_ord){ 69 tree2[pos]+=val; 70 pos+=lowbit(pos); 71 } 72 } 73 void get_ans(int u){ 74 for(int i=0;i<Edge[u].size();i++){ 75 int to=Edge[u][i]; 76 ans+=sum_tree1(R[to])-sum_tree1(L[to]+1-1)+sum_tree2(L[to]); // 查询的时候注意to的范围界定，不要算重复 77 add_tree1(L[to],1); // tree1保存的是后序trie树上，满足以to为根节点的子树中人的个数 78 add_tree2(L[to],1); // tree2保存的是后序trie树上，以根节点到to形成的字符串 为前缀的人的个数 79 add_tree2(R[to]+1,-1); // 这里之所以-1的原因是tree2保存的是满足以根节点到to形成的字符串的前缀的个数，如果不是to这个节点的子树中的点的话，就没有必要+1了，所以这里是区间更新 80 } 81 for(int i=0;i<26;i++){ 82 int to=ch_pre[u][i]; 83 if(!to)continue; 84 get_ans(to); 85 } 86 for(int i=0;i<Edge[u].size();i++){ 87 int to=Edge[u][i]; 88 add_tree1(L[to],-1);//每查询完一条删除记录 89 add_tree2(L[to],-1); 90 add_tree2(R[to]+1,1); 91 } 92 } 93 char str[maxn]; 94 signed main(){ 95 int n; 96 scanf("%lld",&n); 97 for(int i=1;i<=n;i++){ 98 scanf("%s",str); 99 int u=add_ch_pre(str); 100 int v=add_ch_suf(str); 101 Edge[u].push_back(v); 102 } 103 dfs(0); 104 get_ans(0); 105 printf("%lld ",ans); 106 return 0; 107 }
学习网址：https://blog.csdn.net/ac_machine/article/details/79382247