bzoj 3796 Mushroom追妹纸——后缀数组

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3796

长度一般都是 1e5 ,看这个是 5e4 ,一看就是把两个串接起来做。

自己本来想的是把 s3 分别接到 s1 和 s2 后面,做后缀数组求出 s1 和 s2 的每个位置有没有作为开头出现了 s3 ;然后把 s1 和 s2 接起来做后缀数组,二分一个长度作为答案,按 sa[ ] 的顺序遍历每个位置,遇到 s2 的就记录一下它能不能让之后的 s1 和某个 s2 的 LCP >= ans_len ,遇到 s1 就看有没有 s2 和它的 LCP >= ans_len (O(1)),有的话再看看 s1 对应的那个位置后面 ans_len 区域内有没有完整地出现 s3 (可以给每个位置记录 lst[ ] 表示最近的下一个 s3 开头出现的位置),如果没有的话,这个 ans_len 可行;还要倒着做一遍统计后面的 s2 对前面的 s1 的影响。

看了一下题解。原来不用二分答案,因为可以取尽量大的更新答案;而且对于一个 s1 ,最好的 s2 一定是离它最近的 s2 ,因为 LCP 越远越短了;找到一个 LCP 之后,就算后面对应区域内出现了完整的 s3 也不用认为这个 LCP 不合法,可以让 LCP 和不含 s3 部分的长度取 min 来更新答案。

而且算 s1 和 s2 的每个位置有没有作为开头出现 s3 也可以不用后缀数组,做 kmp 即可。

正着和倒着做也可以等价为正着同时统计 s2 对 s1 的影响和 s1 对 s2 的影响。大概是记录 mn1 和 mn2 分别表示 s1 能给出多少贡献和 s2 能给出多少贡献,那么遇到一个 s1 的位置,可以让 mn1 = INF , mn2 = min( mn2 , ht[ i ] ) ;因为 i 位置能否贡献是看从 i+1 开始的 ht[ ] 取 min 的。

注意数组大小。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e4+5,M=1e5+5,M2=1e4+5,K=20;
int sa[M],rk[M],tp[M],tx[M],ht[M],lst[M],nxt[M+M2];
char s[M+M2],s1[N],s2[N],s3[N];
int Mn(int a,int b){return a<b?a:b;}
int Mx(int a,int b){return a>b?a:b;}
void kmp(int m3,int m1,int m2)
{
  int n=m1+m2+m3+2;
  for(int i=2;i<=n;i++)
    {
      int cr=nxt[i-1];
      while(cr&&s[cr+1]!=s[i])cr=nxt[cr];
      if(s[cr+1]==s[i])nxt[i]=cr+1;
      if(nxt[i]==m3)
    lst[i-m3-1-m3+1]=1;
    }
  lst[m1+m2+2]=m1+m2+2;
  for(int i=m1+m2+1;i;i--)
    lst[i]=(lst[i]?i:lst[i+1]);
}
void Rsort(int n,int nm)
{
  for(int i=1;i<=nm;i++)tx[i]=0;
  for(int i=1;i<=n;i++)tx[rk[i]]++;
  for(int i=2;i<=nm;i++)tx[i]+=tx[i-1];
  for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i];
}
void get_sa(int n)
{
  int nm=27;
  for(int i=1;i<=n;i++)tp[i]=i,rk[i]=s[i]-‘a‘+1;
  Rsort(n,nm);
  for(int k=1;k<=n;k<<=1)
    {
      int tot=0;
      for(int i=n-k+1;i<=n;i++)tp[++tot]=i;
      for(int i=1;i<=n;i++)
    if(sa[i]>k)tp[++tot]=sa[i]-k;
      Rsort(n,nm);memcpy(tp,rk,sizeof rk);
      nm=1;rk[sa[1]]=1;
      for(int i=2,u,v;i<=n;i++)
    {
      u=sa[i]+k;v=sa[i-1]+k;if(u>n)u=0;if(v>n)v=0;
      rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm;
    }
      if(nm==n)break;
    }
}
void get_ht(int n)
{
  for(int i=1,k=0,j;i<=n;i++)
    {
      for(k?k--:0,j=sa[rk[i]-1];i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++);
      ht[rk[i]]=k;//rk[i]!!
    }
}
void calc(int ps,int len,int &ans,int m3)
{
  int ret=Mn(len,lst[ps]-ps+m3-1);
  ans=Mx(ans,ret);
}
int main()
{
  scanf("%s",s1+1);scanf("%s",s2+1);scanf("%s",s3+1);
  int m1=strlen(s1+1),m2=strlen(s2+1),m3=strlen(s3+1),n=m1+m2+1;
  memcpy(s,s3,sizeof s3);s[m3+1]=‘,‘;
  for(int i=m3+2,j=1;j<=m1;j++,i++)s[i]=s1[j];
  s[m3+1+m1+1]=‘!‘;//don‘t be the same with s[m3+1]
  for(int i=m3+1+m1+1+1,j=1;j<=m2;j++,i++)s[i]=s2[j];
  kmp(m3,m1,m2);
  memcpy(s,s1,sizeof s1);s[m1+1]=‘z‘+1;
  for(int i=m1+2,j=1;j<=m2;j++,i++)s[i]=s2[j];
  get_sa(n);get_ht(n); int ans=0;
  for(int i=1,mn1=0,mn2=0;i<=n;i++)
    {
      if(sa[i]<=m1)
    {
      mn1=n; mn2=Mn(mn2,ht[i]);
      calc(sa[i],mn2,ans,m3);
    }
      else if(sa[i]>m1+1)
    {
      mn2=n; mn1=Mn(mn1,ht[i]);
      calc(sa[i],mn1,ans,m3);
    }
    }
  printf("%d\n",ans);
  return 0;
}

原文地址:https://www.cnblogs.com/Narh/p/10085846.html

时间: 12-07

bzoj 3796 Mushroom追妹纸——后缀数组的相关文章

BZOJ 1692: [Usaco2007 Dec]队列变换 [后缀数组 贪心]

1692: [Usaco2007 Dec]队列变换 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1383  Solved: 582[Submit][Status][Discuss] Description FJ打算带他的N(1 <= N <= 30,000)头奶牛去参加一年一度的“全美农场主大奖赛”.在这场比赛中,每个参赛者都必须让他的奶牛排成一列,然后领她们从裁判席前依次走过. 今年,竞赛委员会在接受队伍报名时,采用了一种新的登记规则:他们把所

BZOJ 1031: [JSOI2007]字符加密Cipher 后缀数组

1031: [JSOI2007]字符加密Cipher Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 6014  Solved: 2503[Submit][Status][Discuss] Description 喜欢钻研问题的JS同学,最近又迷上了对加密方法的思考.一天,他突然想出了一种他认为是终极的加密办法 :把需要加密的信息排成一圈,显然,它们有很多种不同的读法.例如下图,可以读作: JSOI07 SOI07J OI07JS I07JSO 0

利用WiFi钓鱼法追邻居漂亮妹纸

假设,你的邻居是一个妹纸.漂亮单身,你,技术狗,家穷人丑,集体户口.像借酱油这种老套搭讪方式的成功率对你来说实在很低. 你要做的是了解她,然后接近她.通过搜集更多的情报,为创造机会提供帮助. 初级情报搜集 这个没技术含量.人人可用. 一个人只要活在世上,就会留下痕迹.痕迹当中蕴含着情报,专业的情报人员都有着无比的好奇心和洞察力. 她会把垃圾袋放在门口,等出门的时候扔掉. 夜深人静,你悄悄的把垃圾袋偷走,找到了里边的快递包裹.于是你得到了她的电话号码和名字. 是假名怎么办?通过手机充值软件,可以通

BZOJ 3238 AHOI 2013 差异 后缀数组+单调栈

题目大意: 思路:一看各种后缀那就是后缀数组没跑了. 求出sa,height之后就可以乱搞了.对于height数组中的一个值,height[i]来说,这个值能够作为lcp值的作用域只在左边第一个比他小的位置到右边第一个比他小的位置.这个东西很明显可以倍增RMQ+二分/单调栈. 之后就是数学题了 Σlen[Ti] + len[Tj] = (len + 1) * len * (len - 1),之后吧所有求出来的Σ2 * lcp(Ti,Tj)减掉就是答案. 记得答案开long long CODE:

后缀数组 hash求LCP BZOJ 4310: 跳蚤

后缀数组的题博客里没放进去过..所以挖了一题写写 充实下博客 顺便留作板子.. 一个字符串S中 内容不同的子串 有 sigma{n-sa[i]+1-h[i]}   (噢 这里的h[]就是大家熟知的height[]) 所以l=1,r=上述sigma 二分 答案是字典序第几大的子串. 然后 求S中第k大的子串W : 因为h[i]是与i-1有关的 所以要从n downto 1,k-=n-sa[i]+1-h[i] 至 k再减就非正了 显然这样扫过来 子串字典序是递减的  因此可以得到第k大子串W 然后再

BZOJ 4199: [Noi2015]品酒大会( 后缀数组 + 并查集 )

求出后缀数组后, 对height排序, 从大到小来处理(r相似必定是0~r-1相似), 并查集维护. 复杂度O(NlogN + Nalpha(N)) ----------------------------------------------------------------------------------- #include<cstdio> #include<cstring> #include<algorithm> using namespace std; ty

BZOJ 3230: 相似子串( RMQ + 后缀数组 + 二分 )

二分查找求出k大串, 然后正反做后缀数组, RMQ求LCP, 时间复杂度O(NlogN+logN) --------------------------------------------------------------------- #include<cstdio> #include<algorithm> #include<cstring> #include<cctype> using namespace std; typedef long long

bzoj 2251: [2010Beijing Wc]外星联络 后缀数组

2251: [2010Beijing Wc]外星联络 Time Limit: 30 Sec  Memory Limit: 256 MBSubmit: 424  Solved: 232[Submit][Status][Discuss] Description 小 P 在看过电影<超时空接触>(Contact)之后被深深的打动,决心致力于寻 找外星人的事业.于是,他每天晚上都爬在屋顶上试图用自己的收音机收听外星 人发来的信息.虽然他收听到的仅仅是一些噪声,但是他还是按照这些噪声的高 低电平将接收到

BZOJ 2119 股市的预测 后缀数组

题目大意:给定一个序列,求差分后有多少个子串满足形式为ABA,其中B部分长度为m,A部分长度大于0 首先枚举A的长度j,将序列上每隔j个点插入一个关键点 对于第i个位置上的关键点,我们找到第i+j+m个位置 利用后缀数组找出两个位置向左拓展多少个位置都是相同的,以及向右拓展都少个位置都是相同的 为了保证不重复向左和向右最多拓展j-1个位置 设拓展之后长度为len,那么如果len>=j,ans+=(len-j+1) 如图,拓展出的区域长度为5,j=4,则可以找到两个子串 其中两个a虽然相同,但是由

BZOJ 3998 后缀数组

思路: 第一问 建出来后缀数组以后  前缀和一发n-sa[i]-ht[i]+1  二分 第二问 二分判断是带重复的第几 怎么判断呢   找到它  往后扫ht递减sum+=它   跟K判判 注意等于 加一 之类的各种坑爹细节 要死.. //By SiriusRen #include <bits/stdc++.h> using namespace std; const int N=1000050; int n,cntA[N],cntB[N],A[N],B[N],rk[N],sa[N],tsa[N]