[noi1760]SAM

建立SAM，求出每一个节点最左边的出现位置（即right集合中的最小元素，在树上dfs即可）

枚举左端点i和右端点j（保证j是最小的满足$s[i,j)$不是$s[0,i)$的子串），维护k表示$s[i,j)$所对应的位置，$i+1$可以通过找到$nex[k]$来实现，$j+1$直接在SAM上走即可，显然j单调不减，利用单调性维护即可

求出每一个i所对应的j后，可以直接用区间修改在线段树上做，但由于i单调不减，因此从上一个赋值的位置到这里暴力即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2000005

 4 #define L (k<<1)

 5 #define R (L+1)

 6 #define mid (l+r>>1)

 7 vector<int>v[N];

 8 int V,las,n,nex[N],len[N],mn[N],ch[N][2],f[N<<2];

 9 char s[N];

10 void add(int c){

11     int p=las,np=las=++V;

12     len[np]=len[p]+1;

13     while ((p)&&(!ch[p][c])){

14         ch[p][c]=np;

15         p=nex[p];

16     }

17     if (!p)nex[np]=1;

18     else{

19         int q=ch[p][c];

20         if (len[q]==len[p]+1)nex[np]=q;

21         else{

22             int nq=++V;

23             len[nq]=len[p]+1;

24             nex[nq]=nex[q];

25             nex[q]=nex[np]=nq;

26             memcpy(ch[nq],ch[q],sizeof(ch[q]));

27             while ((p)&&(ch[p][c]==q)){

28                 ch[p][c]=nq;

29                 p=nex[p];

30             }

31         }

32     }

33 }

34 void dfs(int k){

35     for(int i=0;i<v[k].size();i++){

36         dfs(v[k][i]);

37         mn[k]=min(mn[k],mn[v[k][i]]);

38     }

39 }

40 void down(int k){

41     f[L]=min(f[L],f[k]);

42     f[R]=min(f[R],f[k]);

43 }

44 void update(int k,int l,int r,int x,int y,int z){

45     if ((l>y)||(x>r))return;

46     if ((x<=l)&&(r<=y)){

47         f[k]=min(f[k],z);

48         return;

49     }

50     update(L,l,mid,x,y,z);

51     update(R,mid+1,r,x,y,z);

52 }

53 void query(int k,int l,int r){

54     if (l==r){

55         printf("%d\n",max(l-f[k],0));

56         return;

57     }

58     down(k);

59     query(L,l,mid);

60     query(R,mid+1,r);

61 }

62 int main(){

63     scanf("%s",s);

64     n=strlen(s);

65     V=las=1;

66     memset(mn,0x3f,sizeof(mn));

67     for(int i=0;i<n;i++){

68         add(s[i]-'0');

69         mn[las]=i;

70     }

71     for(int i=2;i<=V;i++)v[nex[i]].push_back(i);

72     dfs(1);

73     memset(f,0x3f,sizeof(f));

74     for(int i=0,j=0,k=1;i<n;j=max(j,++i)){

75         for(;(j<n)&&(mn[ch[k][s[j]-'0']]<i);k=ch[k][s[j++]-'0']);

76         if (i<j)update(1,1,n,i+1,j,i);

77         if ((k>1)&&(j-i-1<=len[nex[k]]))k=nex[k];

78     }

79     query(1,1,n);

80 }

巴特西

[noi1760]SAM

最新文章

热门文章