题目大意
你有一个字符串S，开始为空，现在有两种操作：
1. 在S后面加入一个字符c
2. 删除S最后一个字符（保证进行该操作时S不为空）
每次操作后输出当前S中有多少个不同的连续子串。
操作数不大于100000
在线做法
这道题可以离线建trie，然后打个sam。（然而我打的是在线）
在线维护字符串，维护插入、删除操作，很容易想到后缀平衡树。
如果字符串是静态的，统计S中不同子串个数的经典做法是用后缀数组，构造出height数组后统计答案。
【后缀平衡树|hashit】由于后缀平衡树维护后缀的顺序，所以现在我们可以动态算height数组。采用hash，可以二分height[i]的大小，然后hash判断两个后缀相同长度的连续一段是否相同即可。
时间复杂度O(nlogn)
#include
#include
#include
#include using namespace std;
const int maxn=100005,mo=5371297,pri=832189,M[2]={67,71};
typedef long long LL;
typedef unsigned long long ULL;
const LL Inf=(LL)1<<60;
int n,root,fa[maxn],son[maxn][2],fix[maxn],len,pre[maxn],nxt[maxn],height[maxn];
LL l[maxn],r[maxn],rank[maxn],ans;
ULL Hash[2][maxn],Power[2][maxn];
char s[maxn],c[maxn];
void rebuild(int x,LL L,LL R)
{
if (!x) return;
l[x]=L;
r[x]=R;
rank[x]=l[x]+r[x];
rebuild(son[x][0],l[x],rank[x]>>1);
rebuild(son[x][1],rank[x]>>1,r[x]);
}void Rotate(int x,int t,LL l,LL r)
{
int y=fa[x];
if (y==root) root=x;
else
{
if (son[fa[y]][0]==y) son[fa[y]][0]=x;
else son[fa[y]][1]=x;
}
fa[x]=fa[y];
son[y][t]=son[x][t^1];
fa[son[y][t]]=y;
son[x][t^1]=y;
fa[y]=x;
rebuild(x,l,r);
}bool cmp(int x,int y)
{
return s[x]1]y) x^=y^=x^=y;
int l,r,mid;
for (l=1,r=x+1,mid=l+r>>1;
l>1)
if (Same(x,y,mid)) l=mid+1;
else r=mid;
return l-1;
}void update(int x)
{
ans-=nxt[x]-height[nxt[x]];
height[x]=lcp(x,pre[x]);
height[nxt[x]]=lcp(nxt[x],x);
ans+=x-height[x]+nxt[x]-height[nxt[x]];
}void insert(int x,int i,LL l,LL r)
{
LL mid=l+r>>1;
if (cmp(x,i))
{
if (son[i][0]) insert(x,son[i][0],l,mid);
else
{
son[i][0]=x;
fa[x]=i;
rebuild(x,l,mid);
pre[x]=pre[i];
nxt[pre[x]]=x;
nxt[x]=i;
pre[i]=x;
}
if (fix[i]>fix[son[i][0]]) Rotate(son[i][0],0,l,r);
}else
{
if (son[i][1]) insert(x,son[i][1],mid,r);
else
{
son[i][1]=x;
fa[x]=i;
rebuild(x,mid,r);
nxt[x]=nxt[i];
pre[nxt[x]]=x;
pre[x]=i;
nxt[i]=x;
}
if (fix[i]>fix[son[i][1]]) Rotate(son[i][1],1,l,r);
}
}void Delete(int x)
{
while (son[x][0]>0 || son[x][1]>0)
if (!son[x][0] || son[x][1]>0 && fix[son[x][0]]>fix[son[x][1]]) Rotate(son[x][1],1,l[x],r[x]);
else Rotate(son[x][0],0,l[x],r[x]);
if (root==x) root=0;
else
{
ans-=x-height[x]+nxt[x]-height[nxt[x]];
if (x==son[fa[x]][0]) son[fa[x]][0]=0;
else son[fa[x]][1]=0;
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
height[nxt[x]]=min(height[nxt[x]],height[x]);
//height[nxt[x]]=lcp(nxt[x],pre[x]);
ans+=nxt[x]-height[nxt[x]];
}
}int main()
{
scanf("%s",c+1);
n=strlen(c+1);
Power[0][0]=Power[1][0]=1;
for (int i=1;
i<=n;
i++)
for (int j=0;
j<2;
j++) Power[j][i]=Power[j][i-1]*M[j];
for (int i=1;
i<=n;
i++)
{
if (c[i]=='-') Delete(len--);
else
{
s[++len]=c[i];
fix[len]=ran(len);
fa[len]=son[len][0]=son[len][1]=0;
for (int j=0;
j<2;
j++) Hash[j][len]=Hash[j][len-1]*M[j]+s[len]-'a';
if (len==1)
{
root=1;
l[1]=0;
rank[1]=r[1]=Inf;
ans=1;
printf("1\n");
continue;
}
insert(len,root,0,Inf);
update(len);
}
printf("%lld\n",ans);
}
return 0;
} 推荐阅读
- Asp.net|System.Globalization.DateTimeFormatInfo.InvariantInfo
- Android|Android VideoView如何播放RTSP的流
- 技术学习|Tomcat 内存泄露问题
- Android基础|Android中Spinner下拉列表（使用ArrayAdapter和自定义Adapter实现）
- 软件编程|getopt的使用
- android|android 简单按键修改
- xml|读取xml文件中的内容到HashTable
- Android-例子|初学Android实现打电话的功能-使用Intent和AndroidManifset.xml中加入权限
- memcmp源码