最好的dm单网站建设,深圳做网站500元,wordpress应用展示,wordpress iis 404阿狸的打字机
题解
题目中给出的字符串就是构建TrieTrieTrie树的顺序.我们将字符串依次读入,每读入一个小写字符就相当于在TrieTrieTrie树当前节点下插入一个小写字符,读入BBB时,就在TrieTrieTrie树中向父节点移动一步.读入PPP的时候,就做一个标记.
然后对这颗TrieTrieTrie树…阿狸的打字机
题解
题目中给出的字符串就是构建TrieTrieTrie树的顺序.我们将字符串依次读入,每读入一个小写字符就相当于在TrieTrieTrie树当前节点下插入一个小写字符,读入BBB时,就在TrieTrieTrie树中向父节点移动一步.读入PPP的时候,就做一个标记.
然后对这颗TrieTrieTrie树构建ACACAC自动机.
找找规律发现第xxx串在第yyy串中出现的次数就是TrieTrieTrie树上xxx串尾点到yyy串末尾点的树链上,所有能直接或间接通过failfailfail指针跳到xxx串末尾点的点的个数.
观察到自动机上failfailfail指针构成了一颗failfailfail树.
进一步我们发现,所有能直接或间接跳到xxx串末尾点的点就是failfailfail树上,xxx节点的子树大小.
而实际的答案就是failfailfail树上xxx串末尾点的子树与TrieTrieTrie树上xxx到yyy的树链的交集中点的个数.
我们对failfailfail树做一遍dfsdfsdfs序,用这个dfsdfsdfs序就可以查询和维护failfailfail树的子树的信息了.
对这个dfsdfsdfs序列建立一个树状数组.
然后我们对TrieTrieTrie树做一遍dfsdfsdfs,在dfsdfsdfs的过程中,把当前点在树状数组中的dfndfndfn位置111,返回的时候在该位置−1-1−1,这样相当于在TrieTrieTrie树中从当前点到根节点的树链上所有节点都已经在树状数组中激活了,对于当前点作为yyy的询问,在failfailfail树的以xxx为根的子树中计算有多少个点被激活就ok了(树状数组查询前缀和).
代码
#include iostream
#include algorithm
#include cstring
#include queue
#include vector
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
#define LETTER 26
typedef std::pairint,int pii;
const int N 100010;
char s[N];
struct Trie{int num,fail,fa;int next[LETTER];
}pool[N];
Trie* const trie pool 1;
int cnt;
void init() {cnt 0;memset(pool,0,2*sizeof(Trie));trie[0].fail -1;
}
int now;
int pat[N];
int pc;
std::vectorint trie_edge[N];
void build() {pc now 0;for(int i 0;s[i];i) {if(s[i] B) now trie[now].fa;else if(s[i] P) pat[pc] now;else {int pos trie[now].next[s[i]-a];if(!pos) {pos cnt;memset(trie[pos],0,sizeof(Trie));trie[pos].fa now;trie_edge[now].push_back(pos);}now pos;}}std::queueint Q;Q.push(0);while(!Q.empty()) {int t Q.front();Q.pop();for(int i 0;i LETTER;i) {int cur trie[t].next[i];if(cur) {Q.push(cur);trie[cur].fail trie[trie[t].fail].next[i];}else cur trie[trie[t].fail].next[i];}}
}
int bitree[N1];
int lowbit(int x) {return x (-x);}
int sum(int pos) {int res 0;for(;pos;pos - lowbit(pos)) res bitree[pos];return res;
}
void add(int pos,int x) {for(;pos N1;pos lowbit(pos))bitree[pos] x;
}std::vectorint edge[N];
int beg[N],end[N];
int idx 0;
void dfs1(int u){beg[u] idx;for(int v : edge[u]) dfs1(v);end[u] idx;
}
std::vectorpii query[N];
int ans[N];
void dfs2(int u) {add(beg[u],1);for(pii p : query[u]) {int x p.first,id p.second;ans[id] sum(end[x])-sum(beg[x]-1);}for(int v : trie_edge[u])dfs2(v);add(beg[u],-1);
}int main() {init();std::ios::sync_with_stdio(false);std::cin s;build();for(int i 1;i cnt;i) edge[trie[i].fail].push_back(i);dfs1(0);int m;std::cin m;for(int i 1;i m;i) {int x,y;std::cin x y;query[pat[y]].push_back((pii){pat[x],i});}dfs2(0);for(int i 1;i m;i) {std::cout ans[i] std::endl;}return 0;
}
