F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 2555. -- SubString

2555: SubString

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 3568  Solved: 1073
[Submit][Status][Discuss]

Description

  
    懒得写背景了,给你一个字符串init,要求你支持两个操作
    
    (1):在当前字符串的后面插入一个字符串
    
    (2):询问字符串s在当前字符串中出现了几次?(作为连续子串)
    
    你必须在线支持这些操作。
    

Input

    第一行一个数Q表示操作个数
    
    第二行一个字符串表示初始字符串init
    
    接下来Q行,每行2个字符串Type,Str
    
    Type是ADD的话表示在后面插入字符串。
    
    Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
    
    为了体现在线操作,你需要维护一个变量mask,初始值为0
   
    
    读入串Str之后,使用这个过程将之解码成真正询问的串TrueStr。
    询问的时候,对TrueStr询问后输出一行答案Result
    然后mask = mask xor Result 
    插入的时候,将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压
   

Output

Sample Input

2

A

QUERY B

ADD BBABBBBAAB

Sample Output


0

HINT

 40 % 的数据字符串最终长度 <= 20000,询问次数<= 1000,询问总长度<= 10000

    

100 % 的数据字符串最终长度 <= 600000,询问次数<= 10000,询问总长度<= 3000000


新加数据一组--2015.05.20

   

Source

Ctsc模拟赛By 洁妹

[Submit][Status][Discuss]

HOME Back