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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Hdu4622】【后缀自动机】【Reincarnation】  

2014-04-10 23:26:08|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   取石子的怨念....ToT..
   现在争取做一些模板什么的吧...不求效率只求有0.0
   题目大意:给出一个字符串S,每次询问字符串S【l..r】的不同子串的个数。
   字符串长度 2000,询问10000个。

   这题后缀数组也可以做,需要离线搞。但是复杂度貌似被HDU卡了....所以用后缀自动机应该是最开心的....

   考虑个简单的情况,假设咱们要求【1,m】的不同子串的个数,咱们用后缀自动机怎么做?0.0假设咱们来建立1~m的后缀自动机,咱们的大体思路就是在建立的过程中得到答案。

    那么问题就是如何在建立的过程中得到答案?
    假设咱们已经建立了【1,i】的后缀自动机,然后球出了这里面的不同子串的个数,然后咱们需要添加字符 s[i+1],实际上咱们就在这个子串中新增加了 i+1个s[1..i+1]的后缀,现在咱们的任务实际上就是求这i+1个后缀里面有哪一些在之前已经出现过了,咱们将它减去就可以了。 0.0...然后问题就是i+1个后缀中有多少个和之前出现的子串相同。

    然后咱们先证明一个结论...那就是若以后缀的长度来给后缀标号1,2,...i+1,那么在之前已经出现的后缀构成一个区间【1,k】(k<=i+1),这个是显然的,假设有某个后缀K在之前已经出现过,那么后缀K-1,K-2..1都包含在后缀K里面,自然也都出现过。即,咱们只需要求出之前已经出现过的后缀的最大值即可。

    然而,当咱们看过这个,很容易想到Parent树。一个Parent树上的一个节点到根的Right集合是相互包含的,所以咱们当前的后缀所在的节点实际上在last,然后咱们沿着last往上走,会发现其祖先的Right集合始终包含i+1,也就是说,它的祖先所代表的串都是后缀,然后由于Right集合的性质还可以知道除了它的祖先之外的节点所代表的串必然都不是后缀。所以咱们要找之前出现过的最大的后缀,只需要沿着parent树往上找即可,而实际上由于parent树的节点的step(就是Right集合对应的[min,max]中的max)是离根越近越小,所以最大的后缀实际上就是 last的父亲的step!,所以新增加的子串个数就是     sam[last].step-sam[sam[last].father].step .

    然后就好做了,咱们先给询问按左端点为第一关键字,右端点为第二关键字排序,然后咱们对于每一个可能被询问的左端点,从这个左端点开始都建立一次后缀自动机,并且在建立的过程中得到答案。
    由于字符串长度<=2000,而后缀自动机的建立是O(n)的,最多需要建立O(n)个后缀自动机,所以复杂度就是O(n^2),空间复杂度为O(n)(每一次可以推倒重建),所以这道题就可以AC了。

    由于OJ是远近闻名的专坑P党的HDU......(已经有阴影了233...),所以咱用C++翻译的= =。

    另外这样的题目每一次在add的过程中都要将新建节点np的 go数组memset一下。然后读入下一组数据的时候把sam[1].go memset一下。以前+现在都经常忘记= =

    这里学习到了一个语法0.0...那就是sort的cmp的写法...
    通用公式:


   bool cmp((parameter a, parameter b)
   {
return true if you think a < b;
   }


===============================

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 2010
#define maxq 10010
using namespace std;

struct node{
       int step,par,go[26];
       }sam[maxn*2];

struct query{
       int x,y,ans;
       }q[maxq];

int t,n,ans,tot,last,pos[maxq];
char s[maxn];

bool cmp(int i,int j)
{
     if (q[i].x<q[j].x)return true;
     if (q[i].x==q[j].x&&q[i].y<q[j].y)return true;
     return false;
}

void add(int x)
{
     int np=++tot;
     sam[np].step=sam[last].step+1;
     memset(sam[np].go,0,sizeof(sam[np].go));
     for (;last&&!sam[last].go[x];last=sam[last].par)
       sam[last].go[x]=np;
     if (!last) sam[np].par=1;
         else
         {
           int q=sam[last].go[x];
           if (sam[q].step==sam[last].step+1) sam[np].par=q;
              else
              {
                  int nq=++tot;
                  sam[nq]=sam[q];
                  sam[nq].step=sam[last].step+1;
                  sam[q].par=sam[np].par=nq;
                  for (;last&&sam[last].go[x]==q;last=sam[last].par)
                    sam[last].go[x]=nq;
              }
         } 
     last=np; 
     ans+=sam[last].step-sam[sam[last].par].step;{这一句话不是原自动机模板里面的,而是这道题特有的}
}

void Main()
{
     int i,now;
     scanf("%s",s);
     scanf("%d",&n);
     pos[0]=0;q[0].x=q[0].y=-1;
     for (i=1;i<=n;i++) 
      {
                        scanf("%d%d",&q[i].x,&q[i].y);
                        pos[i]=i;
      }
     sort(pos+1,pos+n+1,cmp);
     for (i=1;i<=n;i++)
     {
         if (q[pos[i]].x!=q[pos[i-1]].x) 
          {
                                         ans=0;now=q[pos[i]].x-1;
                                         tot=last=1;
                                         memset(sam[1].go,0,sizeof(sam[1].go));
                                         sam[1].par=sam[1].step=0;
          }
         while (now<q[pos[i]].y) add(s[now]-'a'),now++;
         q[pos[i]].ans=ans;
     }
     for (i=1;i<=n;i++) printf("%d\n",q[i].ans);
}

int main()
{
    scanf("%d",&t);
    for (;t;t--)
     Main();
    return 0;
}

  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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