E. e-Government

time limit per test:1 second
memory limit per test:256 megabytes
input:standard input
output:standard output

The best programmers of Embezzland compete to develop a part of the project called "e-Government" — the system of automated statistic collecting and press analysis.

We know that any of the k citizens can become a member of the Embezzland government. The citizens' surnames are a1, a2, ..., ak. All surnames are different. Initially all k citizens from this list are members of the government. The system should support the following options:

  • Include citizen ai to the government.
  • Exclude citizen ai from the government.
  • Given a newspaper article text, calculate how politicized it is. To do this, for every active government member the system counts the number of times his surname occurs in the text as a substring. All occurrences are taken into consideration, including the intersecting ones. The degree of politicization of a text is defined as the sum of these values for all active government members.

Implement this system.


The first line contains space-separated integers n and k (1 ≤ n, k ≤ 105) — the number of queries to the system and the number of potential government members.

Next k lines contain the surnames a1, a2, ..., ak, one per line. All surnames are pairwise different.

Next n lines contain queries to the system, one per line. Each query consists of a character that determines an operation and the operation argument, written consecutively without a space.

Operation "include in the government" corresponds to the character "+", operation "exclude" corresponds to "-". An argument of those operations is an integer between 1 and k — the index of the citizen involved in the operation. Any citizen can be included and excluded from the government an arbitrary number of times in any order. Including in the government a citizen who is already there or excluding the citizen who isn't there changes nothing.

The operation "calculate politicization" corresponds to character "?". Its argument is a text.

All strings — surnames and texts — are non-empty sequences of lowercase Latin letters. The total length of all surnames doesn't exceed106, the total length of all texts doesn't exceed 106.


For any "calculate politicization" operation print on a separate line the degree of the politicization of the given text. Print nothing for other operations.


7 3







using namespace std;
#define MAXN 1000100
int K,N,loc[MAXN],visit[MAXN];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
char S[MAXN];
namespace FailTree
int son[MAXN][],end[MAXN],sz=,fail[MAXN];
#define id(str) str-'a'+1
inline int Insert(int x,char str[])
int len=strlen(str+),now=;
for (int i=; i<=len; i++)
if (son[now][id(str[i])]) now=son[now][id(str[i])];
else son[now][id(str[i])]=++sz,now=sz;
end[now]=; loc[x]=now;
inline void Getfail()
while (!q.empty())
int now=q.front(); q.pop();
for (int i=; i<=; i++)
if (son[now][i])
int fa=fail[now];
while (fa && !son[fa][i]) fa=fail[fa];
fail[son[now][i]]=fa? son[fa][i]:;
for (int i=; i<=sz; i++) InsertEdge(fail[i],i);
using namespace FailTree;
namespace Divide
int pl[MAXN],pr[MAXN],dfn,tree[MAXN<<];
inline void DFS(int now,int last)
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
inline int lowbit(int x) {return x&-x;}
inline void Modify(int pos,int D) {for (int i=pos; i<=dfn; i+=lowbit(i)) tree[i]+=D;}
inline int Query(int pos) {int re=; for (int i=pos; i; i-=lowbit(i)) re+=tree[i]; return re;}
inline int Calc(char str[])
int len=strlen(str+),ans=,now=;
for (int i=; i<=len; i++)
while (now && !son[now][id(str[i])]) now=fail[now];
now=now? son[now][id(str[i])]:;
return ans;
inline void Change(int x,int D)
if (visit[x] && D>) return;
if (!visit[x] && D<) return;
Modify(pl[loc[x]],D); Modify(pr[loc[x]],-D);
using namespace Divide;
int main()
for (int i=; i<=N; i++) scanf("%s",S+),Insert(i,S);
Getfail(); DFS(,);
for (int i=; i<=N; i++) Modify(pl[loc[i]],),Modify(pr[loc[i]],-),visit[i]=;
while (K--)
char opt=getchar(); int x;
while (opt!='+' && opt!='-' && opt!='?') opt=getchar();
switch (opt)
case '+' : scanf("%d",&x); Change(x,); break;
case '-' : scanf("%d",&x); Change(x,-); break;
case '?' : scanf("%s",S+); printf("%d\n",Calc(S)); break;
return ;


  1. redis集群讨论
  2. DrawerLayout学习,抽屉效果
  3. 模仿angularjs写了一个简单的HTML模版和js数据填充的示例
  4. 【转】iOS设备的UDID是什么?苹果为什么拒绝获取iOS设备UDID的应用?如何替代UDID?
  5. Fresco 源码分析(三) Fresco服务端处理(3) DataSource到Producer的适配器逻辑以及BitmapMemoryCacheProducer处理的逻辑
  6. python - PipeMapRed.waitOutputThreads(): subprocess failed with code 1
  7. 8.20 usaco
  8. [置顶] linux下让php支持mysql——寻找消失的mysql
  9. Swift - 20 - 字典的基础操作
  10. libgdx, mouse 关节
  11. S3C3440看门狗驱动程序
  12. POP音原因
  13. AfxBeginThread和CreateThread具体区别
  14. javascript prop和attr的区别
  15. 【接口时序】3、UART串口收发的原理与Verilog实现
  16. spring cloud config安全
  17. js 数组、对象转json 以及json转 数组、对象
  18. [No0000143]Win10“卓越性能模式”
  19. HDFS只支持文件append操作, 而依赖HDFS的HBase如何完成增删改查功能
  20. Item is not readable svn: 条目不可读


  1. Python (一) 简介、安装
  2. [连载]《C#通讯(串口和网络)框架的设计与实现》- 8.总体控制器的设计
  3. 很强大的HTML+CSS+JS面试题(附带答案)
  4. Gulp自动添加版本号
  5. Hadoop学习日志- install hadoop
  6. Linux下安装Oracle11g服务器
  7. SQLSERVER基础语句(一)
  8. Java中的关键字 transient
  9. SE Springer小组之《Spring音乐播放器》可行性研究报告三、四
  10. ddd 聚合根 之 聚合与不聚合 设计