题目大意:
题解:
这道题我想出了三种做法,不过只有最后一种能过。
第一种:
第二种:
第三种:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 2000010;
int ch[maxn][26],nodecnt;
int mp[maxn];
char s[2000010];
inline void insert(const int &pos){
int len = strlen(s),nw = 0;
for(int i=0;i<len;++i){
int c = s[i] - 'a';
if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;
nw = ch[nw][c];
}mp[pos] = nw;
}
int fail[maxn],q[maxn];
inline void build(){
int l = 0,r = -1;
for(int c=0;c<26;++c){
if(ch[0][c]){
fail[ch[0][c]] = 0;
q[++r] = ch[0][c];
}
}
while(l <= r){
int u = q[l++];
for(int c=0;c<26;++c){
int t = ch[fail[u]][c];
if(!ch[u][c]) ch[u][c] = t;
else{
fail[ch[u][c]] = t;
q[++r] = ch[u][c];
}
}
}
}
struct Edge{
int to,next;
}G[maxn<<1];
int head[maxn],cnt;
void add(const int &u,const int &v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
#define v G[i].to
int fa[maxn],ind[maxn],oud[maxn],dfs_clock;
int siz[maxn],son[maxn],dep[maxn];
void dfs(const int &u){
siz[u] = 1;
for(int i = head[u];i;i=G[i].next){
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs(v);
siz[u] += siz[v];
if(siz[son[u]] < siz[v]) son[u] = v;
}
}
int top[maxn];
void dfs(const int &u,const int &tp){
top[u] = tp;ind[u] = ++dfs_clock;
if(son[u]) dfs(son[u],tp);
for(int i = head[u];i;i=G[i].next){
if(v == son[u] || v == fa[u]) continue;
dfs(v,v);
}oud[u] = dfs_clock;
}
#undef v
inline int lca(int u,int v){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u,v);
u = fa[top[u]];
}return dep[u] < dep[v] ? u : v;
}
#define lowbit(x) (x&-x)
int c[maxn+100];
inline void modify(int x,int y){
for(;x <= dfs_clock + 10;x += lowbit(x)) c[x] += y;
}
inline int query(int x){
int ret = 0;
for(;x;x-=lowbit(x)) ret += c[x];
return ret;
}
int a[maxn];
inline bool cmp(const int &i,const int &j){
return ind[i] < ind[j];
}
inline void find(){
int len = strlen(s),nw = 0;
a[0] = 0;
for(int i = 0;i<len;++i){
nw = ch[nw][s[i] - 'a'];
a[++a[0]] = nw+1;
}sort(a+1,a+a[0]+1,cmp);
int p = 1;
for(int i=1;i<=a[0];++i){
if(a[i] != a[i-1] || i == 1) a[p++] = a[i];
}a[0] = p-1;
for(int i=1;i<=a[0];++i){
modify(ind[a[i]],1);
if(i != a[0]) modify(ind[lca(a[i],a[i+1])],-1);
}
}
int main(){
int n;read(n);
for(int i=1;i<=n;++i){
scanf("%s",s);
insert(i);
}build();
for(int i=1;i<=nodecnt;++i) add(fail[i]+1,i+1);
dfs(1);dfs(1,1);
int m;read(m);
int op;
while(m--){
read(op);
if(op == 1){
scanf("%s",s);
find();
}else{
read(op);
printf("%d\n",query(oud[mp[op]+1]) - query(ind[mp[op]+1]-1));
}
}
getchar();getchar();
return 0;
}