注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2555]SubString  

2015-05-14 15:06:32|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2555: SubString

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 632  Solved: 216
[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

Source

Solution

插入一个字符以后,要将它到S的fail路径上的点全部加1,这个可以用LCT维护fail树。
不过好像暴力跑得更快233.还有这题只有两种字符233

Code

/**************************************************************
    Problem: 2555
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2520 ms
    Memory:25416 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1200010
char s[N],op;
int q,S=1,tot=1,las=1,ch[N][26],fail[N],len[N],cnt[N],mask,i,j,ans;
void add(char c){
    int p=las,np=++tot;
    for(len[np]=len[p]+1;p&&!ch[p][c];p=fail[p])ch[p][c]=np;
    if(las=np,!p)fail[np]=S;
    else if(len[p]+1==len[ch[p][c]])fail[np]=ch[p][c];
    else{
        int q=ch[p][c],r=++tot;
        len[r]=len[p]+1;fail[r]=fail[q];fail[np]=fail[q]=r;cnt[r]=cnt[q];
        memcpy(ch[r],ch[q],sizeof(ch[q]));
        for(;p&&ch[p][c]==q;p=fail[p])ch[p][c]=r;
    }
    for(p=las;p;p=fail[p])cnt[p]++;
}
void decode(int mask,int i){
    for(int j=0;s[j];j++){
        mask=(mask*131+j)%i;
        std::swap(s[j],s[mask]);
    }
}
int main(){
    scanf("%d\n",&q);
    for(gets(s);s[i];i++)add(s[i]-'A');
    for(;q--;){
        while(op=getchar(),op!='A'&&op!='Q');
        scanf("%*s%s",s);
        for(i=0;s[i];i++);
        decode(mask,i);
        if(op=='A'){
            for(i=0;s[i];i++)add(s[i]-'A');
        }
        else{
            for(i=0,j=S;s[i];i++)
            if(ch[j][s[i]-'A']==0){
                ans=0;
                goto outp;
            }
            else j=ch[j][s[i]-'A'];
            ans=cnt[j];
            outp:printf("%d\n",ans),mask^=ans;
        }
    }
}
  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018