【Hihocoder1413】Rikka with String(后缀自动机)
string with 后缀 自动机
2023-09-11 14:14:40 时间
【Hihocoder1413】Rikka with String(后缀自动机)
题面
Hihocoder
给定一个小写字母串,回答分别把每个位置上的字符替换为'#'后的本质不同的子串数。
题解
首先横跨'#'左右的串一定恰好只会出现一次,所以直接统计答案。
那么剩下的部分就是左右的本质不同的子串数。
我们把答案拆成三个部分,先是左侧本质不同子串的个数,再是右侧本质不同子串的个数。最后再减去既在左侧出现过,又在右侧出现过的串的个数。
左右两个直接用\(SAM\)算就好了。
在两侧同时出现过的,我们维护每一个节点最小的\(endpos\)和最大的\(endpos\),显然'#'出现在两串之间的时候就会在左右同时被计算。
每个\(endpos\)表示的都是一段区间,这里就是做多个区间的区间加,所以二阶差分计算。
具体的东西看代码。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
#define MAX 300300
int n;char ch[MAX];
struct Node
{
int son[26];
int ff,len;
}t[MAX<<1];
int last=1,tot=1;
ll ans[MAX],c1[MAX],c2[MAX],cnt=0;
int l[MAX<<1],r[MAX<<1];
void extend(int c,int id)
{
int p=last,np=++tot;last=np;
t[np].len=t[p].len+1;
while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;
if(!p)t[np].ff=1;
else
{
int q=t[p].son[c];
if(t[q].len==t[p].len+1)t[np].ff=q;
else
{
int nq=++tot;
t[nq]=t[q];t[nq].len=t[p].len+1;
t[q].ff=t[np].ff=nq;
while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
}
}
cnt+=t[np].len-t[t[np].ff].len;
l[np]=r[np]=id;
}
int a[MAX<<1],p[MAX<<1];
int main()
{
scanf("%d",&n);scanf("%s",ch+1);
memset(l,63,sizeof(l));memset(r,0,sizeof(r));
for(int i=1;i<=n;++i)extend(ch[i]-97,i),ans[i+1]+=cnt;
for(int i=1;i<=n;++i)ans[i]+=1ll*i*(n-i+1);
for(int i=1;i<=tot;++i)a[t[i].len]++;
for(int i=1;i<=n;++i)a[i]+=a[i-1];
for(int i=1;i<=tot;++i)p[a[t[i].len]--]=i;
for(int i=tot;i>1;--i)
{
int u=p[i];
l[t[u].ff]=min(l[t[u].ff],l[u]);
r[t[u].ff]=max(r[t[u].ff],r[u]);
int len=min(r[u]-l[u],t[u].len);
if(len<=t[t[u].ff].len)continue;
c1[l[u]+1]+=len-t[t[u].ff].len;
c2[r[u]-t[t[u].ff].len+1]+=1;
c2[r[u]-len+1]-=1;
}
for(int i=1;i<=n;++i)c2[i]+=c2[i-1];
for(int i=1;i<=n;++i)c1[i]+=c1[i-1]+c2[i];
for(int i=1;i<=n;++i)ans[i]-=c1[i];
memset(t,0,sizeof(t));last=tot=1;cnt=0;
for(int i=n;i;--i)extend(ch[i]-97,i),ans[i-1]+=cnt;
for(int i=1;i<=n;++i)printf("%lld ",ans[i]);
puts("");return 0;
}
相关文章
- Java中char和String 的深入理解 - 字符编码
- Leetcode: Reverse Vowels of a String
- JVM系列之:String.intern和stringTable
- 总结了C#中string.format用法。分享给大家供大家参考。具体分析如下:
- 避免string.Format方法的装箱
- C#调用Delphi DLL获取字符串(C# IntPtr 与 string互转 )
- shell中$后加引号有什么用($"string"和$'string')
- 基于人脸识别的考勤系统 — Flask App — With GUI — with source code
- C++ string append方法的常用用法
- [LeetCode] 1016. Binary String With Substrings Representing 1 To N 子串能表示从1到N数字的二进制串
- FileStorage Read String Start With Number Need Quotation Mark 读取数字开头的字符串需要加引号
- C++ printf with std::string
- MariaDB新增数据报错:SQL 错误 [1366] [22007]: (cIncorrect string value: ‘xE5xBCxA0xE4xB8x89‘ for column