一行超人

上一篇好像略长了，于是新开一篇。

SAM填坑

首先当然是后缀树新姿势BZOJ3413

BZOJ1396: 识别子串

我们注意到只出现一次的串在SAM中right集合大小为1。

那我们有一个显然的想法就是把这些串全部拿出来，然后把覆盖范围内的点用这个串的长度更新。区间最值可以线段树。

但是这样是不可行的，因为本质不同的且只出现了一次的串有可能达到O（n^2）。

那么我们就要注意到SAM压缩之后的性质。right集合大小为1，而且一个节点表示字符串集合是[l[fa[i]]+1,l[i]]。

那么就有趣了。我们发现如果朴素的按上面的来更新，记i所表示的字符串集合结束的位置是x。

那么x-l[i]+1在这些更新中只会用到l[i],x-l[i]+2用l[i]-1,x-l[i]+3用l[i]-2,x-l[fa[i]]用l[fa[i]]+1。

发现了什么？给一个区间加上一条线段？然后询问每个点与线段相交的纵坐标最小的值？@HEOI2013 Segment！

当然。我们还有更简单了。因为这相当于给区间加一个斜率固定的线段，所以我们可以直接用线段树打标记维护！！！

然后还有一段x-l[fa[i]]+1……x[i]我们发现这一段在这一坨更新中得到的最优值是l[fa[i]]+1.仍然是区间打标记！！！

然后这题就做完了。

注意right集合大小为1一定有儿子数<=1。

而儿子数<=1并不代表right集合大小为1，因为其本身也可能是一个前缀。

BZOJ2806: [Ctsc2012]Cheat

这题其实很简单啦

首先L是可以二分的。然后我们就判断一个L是否可行。

不妨考虑dp。f[i]表示前i个字符最多匹配多少位。那么有

f[i]=max(f[i-1],max(f[j]+i-j))其中j+1……i是熟悉的，而i-j>=L。

如果我们能预处理出i最多能往回匹配多少，不妨设为pre[i]，则pre[i]+1……i都是熟悉的。显然pre[i]是单调不减的。那么可以注意到我们就需要维护一个滑动窗口的最大值。而这个窗口的左右端点都是单调不减的。

我们就可以用单调队列来搞辣！

如何计算pre[i]呢？其实非常简单！

我们把标准作文库建成广义SAM。然后就把这个作文放在SAM上跑，顺便记录一下当前匹配了多少。

那么每到一个节点匹配数目就是以该节点为结尾往前最多匹配多少。这个是非常简单的。

然后这道题就做完了

代码大概长这样。。。

struct sam
{
	int last,cnt,l[maxn],go[maxn][2],fa[maxn];
	sam(){last=cnt=1;}
	inline void add(int x)
	{
		int p=last,q;
		if(q=go[p][x])
		{
			if(l[q]==l[p]+1)last=q;
			else 
			{
				int nq=++cnt;l[nq]=l[p]+1;
				memcpy(go[nq],go[q],sizeof(go[q]));
				fa[nq]=fa[q];
				fa[q]=nq;
				for(;p&&go[p][x]==q;p=fa[p])go[p][x]=nq;
				last=nq;
			}
		}else
	    {
	    	int np=++cnt;l[np]=l[p]+1;
	    	for(;p&&!go[p][x];p=fa[p])go[p][x]=np;
	    	if(!p)fa[np]=1;
	    	else
	    	{
	    		q=go[p][x];
	    		if(l[q]==l[p]+1)fa[np]=q;
	    		else
	    		{
	    			int nq=++cnt;l[nq]=l[p]+1;
	    			memcpy(go[nq],go[q],sizeof(go[q]));
	    			fa[nq]=fa[q];
	    			fa[q]=fa[np]=nq;
	    			for(;p&&go[p][x]==q;p=fa[p])go[p][x]=nq;
	    		}
	    	}
	    	last=np;
	    }
	};
	char s[maxn];
	int q[maxn],n,f[maxn],pre[maxn];
	inline void init()
	{
		scanf("%s",s);n=strlen(s);last=1;
		for0(i,n-1)add(s[i]-'0');
	}
	inline bool check(int L)
	{
		f[0]=0;
		int l=1,r=0;
		for1(i,n)
		{
			while(l<=r&&q[l]+1<pre[i])l++;
			f[i]=l>r?0:f[q[l]]+i-q[l];
			f[i]=max(f[i],f[i-1]);
			int j=i-L+1;
			if(j<0)continue;
			while(l<=r&&f[j]-j>f[q[r]]-q[r])r--;
			q[++r]=j;

		}
		return 10*f[n]>=9*n;
	}
	inline void work()
	{
		scanf("%s",s+1);n=strlen(s+1);
		int now=1,y=0;
		for1(i,n)
		{
			int x=s[i]-'0';
			if(go[now][x])now=go[now][x],y++;
			else 
			{
			  while(now&&!go[now][x])now=fa[now];
			  if(!now)now=1,y=0;
			  else y=l[now]+1,now=go[now][x];
		    }
		    pre[i]=i-y+1;
		}
		int l=1,r=n;
		while(l<=r)if(check(mid))l=mid+1;else r=mid-1;
		printf("%d\n",r);
	}
}SAM;
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    int T=read();int G=read();
    while(G--)SAM.init();
    while(T--)SAM.work();
    return 0;
}

BZOJ3756: Pty的字符串

考虑所有子串对ans的贡献，显然每个子串都可以表示成一个前缀的后缀。所以我们直接求出每个前缀的后缀匹配长度。

这个SAM显然可以求，和上一题一起，沿着边走就可以了。

（什么？你说AC自动机也能求？好像真能求。。。哎？好像SAM完全可以取代AC自动机啊

然后我们不妨认为当前走到了now节点，然后匹配长度是len。

那么这len个子串，我们可以分开算。长度<=l[fa[now]]的这个可以直接预处理出fa[now]的这个值，就是从它到根所有子串的出现次数。

然后剩下的ans就是（len-l[fa[now]]）*r[now]。r[now]就是now字符串集合在整个树中出现的次数。

这样就搞完了。

SAM大法好！我是SAM脑残粉！