【bzoj2865】字符串识别 bzoj1396】识别子串

学习了SAM，没有任何感想。。。

传送门

还有一道2865是权限。

题意

给出母串，对于每个位置，找出经过它且只在母串中出现一次的最短字符串长度。

做法

在SAM上只出现一次的串对应的那个节点的$endpos/right$集合中只有一个元素，它一定是$parent$树上的叶子。

找到这些点，他们每个点x都对应着以x对应的一个母串中的位置$posx$为结尾的，长度为$[maxx,minx]$的一些子串，被这些子串覆盖的点都可能被更新答案。那么更新答案的区间就是$[posx-maxx+1,posx]$

有两种情况：

1. 对于位于区间$[posx-maxx+1,posx-minx+1]$中的点y，他的答案可能被更新为$posx-y+1$。开个线段树，存下$posx+1$。
2. 对于位于区间$[posx-minx+1,posx]$中的点z，没得选，他的答案可能被更新为$minx$。开另一颗线段树存下$minx$

那么每个位置单点查询就好了。

一个小问题

2865那个题串长$5e5$，然而内存$128mb$，如果你不想写后缀数组的做法，就需要一些小技巧。

1.用$unordered$_$map$存儿子，因为有些点可能没有26个儿子。

2.把记录每个点是否是叶子的数组改成bool

3.把记录SAM中叶子节点对应的母串位置的数组$pos$改成$map$，因为有些点可能什么都不对应。

4.上面那些优化跟这个比起来都是屑，你可以把数据下下来，发现最大的一个点SAM大小只有84万多，那么把SAM数组大小改成$850000$，嘿嘿嘿。

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<tr1/unordered_map>
using namespace std;
using namespace tr1;
struct SAM{
    int fa,len;
    unordered_map<int,int> ch;
}t[850001];
bool o[850001]; char ch[500001];
int tot=1,last=1,n,lazy1[2000001],lazy2[2000001],num;
unordered_map<int,int> pos;
inline void extend(int x){
    int np=++tot,p=last; last=np;
    t[np].len=t[p].len+1;
    while (p&&!t[p].ch[x]) t[p].ch[x]=np,p=t[p].fa;
    if (!p) t[np].fa=1;
    else{
        int q=t[p].ch[x];
        if (t[q].len==t[p].len+1) t[np].fa=q;
        else{
            int cp=++tot; t[cp]=t[q];
            t[cp].len=t[p].len+1;
            t[q].fa=t[np].fa=cp;
            while (p&&t[p].ch[x]==q) t[p].ch[x]=cp,p=t[p].fa;
        }
    }
    pos[last]=++num;
}
void add1(int rt,int l,int r,int x,int y,int z){
    if (x<=l&&r<=y){
        lazy1[rt]=min(lazy1[rt],z);
        return;
    }
    int mid=(l+r)>>1;
    if (x<=mid) add1(rt<<1,l,mid,x,y,z);
    if (y>mid) add1(rt<<1|1,mid+1,r,x,y,z);
}
void add2(int rt,int l,int r,int x,int y,int z){
    if (x<=l&&r<=y){
        lazy2[rt]=min(lazy2[rt],z);
        return;
    }
    int mid=(l+r)>>1;
    if (x<=mid) add2(rt<<1,l,mid,x,y,z);
    if (y>mid) add2(rt<<1|1,mid+1,r,x,y,z);
}
inline void pushdown1(int rt){
    if (lazy1[rt]==1e9) return;
    lazy1[rt<<1]=min(lazy1[rt],lazy1[rt<<1]);
    lazy1[rt<<1|1]=min(lazy1[rt],lazy1[rt<<1|1]);
    lazy1[rt]=1e9;
}
int query1(int rt,int l,int r,int x){
    if (l==r) return lazy1[rt];
    pushdown1(rt);
    int mid=(l+r)>>1;
    if (x<=mid) return query1(rt<<1,l,mid,x);
    else return query1(rt<<1|1,mid+1,r,x);
}
inline void pushdown2(int rt){
    if (lazy2[rt]==1e9) return;
    lazy2[rt<<1]=min(lazy2[rt],lazy2[rt<<1]);
    lazy2[rt<<1|1]=min(lazy2[rt],lazy2[rt<<1|1]);
    lazy2[rt]=1e9;
}
int query2(int rt,int l,int r,int x){
    if (l==r) return lazy2[rt];
    pushdown2(rt);
    int mid=(l+r)>>1;
    if (x<=mid) return query2(rt<<1,l,mid,x);
    else return query2(rt<<1|1,mid+1,r,x);
}
int main(){
//	freopen("0a.in","r",stdin);
//	freopen("0a.out","w",stdout);
    scanf("%s",ch+1); n=strlen(ch+1);
    for (int i=1; i<=n; i++) extend(ch[i]-'a');
    for (int i=1; i<=tot; i++) o[t[i].fa]=1;
    int l,r;
    memset(lazy1,10,sizeof(lazy1));
    memset(lazy2,10,sizeof(lazy2));
    for (int i=1; i<=tot; i++){
        if (!o[i]){
            l=pos[i]-t[i].len+1,r=pos[i]-t[t[i].fa].len;
            add1(1,1,n,l,r,pos[i]+1);
            add2(1,1,n,r,pos[i],t[t[i].fa].len+1);
        }
    }
    // printf("%d\n",tot);
    for (int i=1; i<=n; i++)
        printf("%d\n",min(query1(1,1,n,i)-i,query2(1,1,n,i)));
    return 0;
}