网站开发流行语言,图标设置wordpress,深圳住房建设部网站,做公司网站注意事项正题
题目链接:https://ac.nowcoder.com/acm/contest/72/F 题目大意 nnn个字符串#xff0c;包括小写字母和#\##。其中#\##可以替换为任意字符串。求有多少对字符串可能相同。
保证每个字符串至少有一个#\##。 2≤n≤500000,∑i1n∣si∣≤1062\leq n\leq 500000,\sum_{i1}^n…正题
题目链接:https://ac.nowcoder.com/acm/contest/72/F 题目大意
nnn个字符串包括小写字母和#\##。其中#\##可以替换为任意字符串。求有多少对字符串可能相同。
保证每个字符串至少有一个#\##。
2≤n≤500000,∑i1n∣si∣≤1062\leq n\leq 500000,\sum_{i1}^n |s_i|\leq 10^62≤n≤500000,∑i1n∣si∣≤106 解题思路
因为可以替换为任意字符串所以只需要考虑第一个#\##前和最后一个#\##后的部分。
在仔细考虑一下这个字符串分成前后的两个部分s,ts,ts,t。数对(x,y)(x,y)(x,y)满足条件当且仅当sxs_xsx是sys_ysy的前缀或者sys_ysy是sxs_xsx的前缀且txt_xtx是tyt_yty的后缀或者tyt_yty是txt_xtx的后缀。
放到两棵TrieTrieTrie树上就是都有祖先关系就好了直接跑第一棵上然后用两个树状数组在第二棵树上维护就好了。
时间复杂度O(mlogm)O(m\log m)O(mlogm) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#define lowbit(x) (x-x)
using namespace std;
const int N1e610;
int n,cnt,pos[N],dfn[N],ed[N];
long long ans;char s[N];
vectorint G[N];
struct TreeBinary{int t[N];void Change(int x,int val){while(xcnt){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;}
}Bf,Bs;
struct Trie{int t[N][26],m1;int Insert(char *s,int n){int x1;for(int i1;in;i){if(s[i]#)break;int cs[i]-a;if(!t[x][c])t[x][c]m;xt[x][c];}return x;}
}Tp,Ts;
void dfs(int x){dfn[x]cnt;for(int i0;i26;i)if(Ts.t[x][i])dfs(Ts.t[x][i]);ed[x]cnt;
}
void work(int x){for(int i0;iG[x].size();i){int pG[x][i];ansBf.Ask(dfn[pos[p]]);Bf.Change(dfn[pos[p]],1);Bf.Change(ed[pos[p]]1,-1);ansBs.Ask(ed[pos[p]])-Bs.Ask(dfn[pos[p]]); Bs.Change(dfn[pos[p]],1);}for(int i0;i26;i)if(Tp.t[x][i])work(Tp.t[x][i]);for(int i0;iG[x].size();i){int pG[x][i];Bs.Change(dfn[pos[p]],-1);Bf.Change(dfn[pos[p]],-1);Bf.Change(ed[pos[p]]1,1);}
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%s,s1);int lstrlen(s1);int xTp.Insert(s,l);G[x].push_back(i);reverse(s1,s1l);pos[i]Ts.Insert(s,l);}dfs(1);work(1);printf(%lld\n,ans);return 0;
}
