后缀数组+单调栈的应用

首先我们研究一下这个表达式,可以发现前半部分与串的情况并没有关系,而只是跟串的长度有关,所以我们先把前半部分算出来:

于是我们只需计算出即可

那么可以发现,对于排名分别为i,j的两个串,他们的lcp应当是:

但是这里的时间复杂度仍然很大

我们换一个角度来思考:如果设,那么我们认为height[k]产生了一个贡献

所以我们可以从每一个height[k]产生了多少贡献的角度来思考,这样就可以把时间复杂度降到O(n)

不难发现,一个k会对一个区间产生贡献的条件就是height[k]是所在区间的最小值

这就可以用单调栈维护了!!

但是要注意,为了防止重复计算,我们对单调栈的两端点的取等条件设成不一样的(即左侧算到第一个height小于等于height[k],右侧算到第一个height小于height[k]的位置)

这样找到每个点向左和向右能延伸的位置lx,rx这样他所占的区间个数就是(i-lx)*(rx-i)

这样去更新就可以了

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
char s[500005];
int sa[500005];
int rank[500005];
int temprank[500005];
int height[500005];
int has[500005];
int v[500005];
int lx[500005],rx[500005];
int l;
bool be_same(int x,int y,int len)
{
return x+len>l||y+len>l||rank[x]!=rank[y]||rank[x+len]!=rank[y+len];
}
void get_sa()
{
int cnt=0;
for(int i=1;i<=l;i++)v[i]=s[i];
for(int i=1;i<=l;i++)has[v[i]]++;
for(int i=0;i<128;i++)if(has[i])temprank[i]=++cnt;
for(int i=1;i<128;i++)has[i]+=has[i-1];
for(int i=1;i<=l;i++)
{
rank[i]=temprank[v[i]];
sa[has[v[i]]--]=i;
}
for(int k=1;cnt!=l;k<<=1)
{
cnt=0;
for(int i=1;i<=l;i++)has[i]=0;
for(int i=1;i<=l;i++)has[rank[i]]++;
for(int i=1;i<=l;i++)has[i]+=has[i-1];
for(int i=l;i;i--)if(sa[i]>k)temprank[sa[i]-k]=has[rank[sa[i]-k]]--;
for(int i=1;i<=k;i++)temprank[l-i+1]=has[rank[l-i+1]]--;
for(int i=1;i<=l;i++)sa[temprank[i]]=i;
for(int i=1;i<=l;i++)temprank[sa[i]]=be_same(sa[i],sa[i-1],k)?++cnt:cnt;
for(int i=1;i<=l;i++)rank[i]=temprank[i];
}
for(int i=1;i<=l;i++)
{
if(rank[i]==1)continue;
int j=max(1,height[rank[i-1]]-1);
while(s[i+j-1]==s[sa[rank[i]-1]+j-1])height[rank[i]]=j++;
}
}
void init()
{
height[0]=height[l+1]=-0x3f3f3f3f;
ll ret=0;
for(int i=1;i<=l;i++)lx[i]=i-1,rx[i]=i+1;
for(int i=2;i<=l;i++)while(height[lx[i]]>height[i])lx[i]=lx[lx[i]];
for(int i=l;i>=2;i--)while(height[rx[i]]>=height[i])rx[i]=rx[rx[i]];
for(int i=2;i<=l;i++)ret+=2*height[i]*(ll)((ll)(rx[i]-i)*(ll)(i-lx[i]));
ll ans=1ll*(l-1)*l/2ll*(l+1);
printf("%lld\n",ans-ret);
}
int main()
{
scanf("%s",s+1);
l=strlen(s+1);
get_sa();
init();
return 0;
}

最新文章

  1. iOS中数据库应用基础
  2. Redis不同类型方法整合
  3. SSRS动态设置文本框属性
  4. DOS批处理不支持将UNC 路径作为当前目录的巧妙解决方案
  5. js中的getAttribute方法使用示例
  6. git status 不可全信
  7. openssl数字证书私钥删除私钥密码
  8. Delphi文件夹的操作
  9. 去除wordpress由代发
  10. jQuery选择器(适合初学者哟....)
  11. Python Web 性能和压力测试 multi-mechanize
  12. [BZOJ 2440] [中山市选2011] 完全平方数 【二分 + 莫比乌斯函数】
  13. android获取View上某点的颜色
  14. vs2010环境下将Win32控制台应用程序,改为Win32项目
  15. screen 实战后台命令执行备份
  16. Grafana是一个可视化面板-安装配置介绍
  17. Windows 系统采用批处理命令修改 ip 地址
  18. Spring MVC国际化
  19. 安装docker ce版
  20. Spring学习笔记——Spring依赖注入原理分析

热门文章

  1. WPF中利用控件的DataContext属性为多个TextBox绑定数据
  2. 谈谈java做登录那些事(一 分析)
  3. python基础5 字典
  4. python之MRO和垃圾回收机制
  5. kotlin电商学习记录,好久没来逛逛了
  6. Windows 7 下安装 docker 应用容器引擎
  7. 【并发编程】【JDK源码】JDK的(J.U.C)java.util.concurrent包结构
  8. Oracle Database 快捷版 安装 连接
  9. mycat 使用
  10. gdb core 调试多线程