1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
| #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; #define MAXN 200006 int n , lst , m; char ch[MAXN]; int ans[MAXN]; struct seg { int T[100000 << 2] , lz[100000 << 2]; void build( ) { memset( T , 0x3f , sizeof T ) , memset( lz , 0x3f , sizeof lz ); } void pd( int rt ) { if( lz[rt] != 0x3f3f3f3f ) { T[rt << 1] = min( T[rt << 1] , lz[rt] ); T[rt << 1 | 1] = min( T[rt << 1 | 1] , lz[rt] ); lz[rt << 1] = min( lz[rt << 1] , lz[rt] ); lz[rt << 1 | 1] = min( lz[rt << 1 | 1] , lz[rt] ); lz[rt] = 0x3f3f3f3f; } } void chkmn( int rt , int l , int r , int L , int R , int c ) { if( L <= l && R >= r ) { lz[rt] = min( lz[rt] , c ) , T[rt] = min( T[rt] , c ); return; } pd( rt ); int m = l + r >> 1; if( L <= m ) chkmn( rt << 1 , l , m , L , R , c ); if( R > m ) chkmn( rt << 1 | 1 , m + 1 , r , L , R , c); } void getit( int rt , int l , int r ) { if( l == r ) { ans[l] = min( ans[l] , T[rt] ); return; } pd( rt ); int m = l + r >> 1; getit( rt << 1 , l , m ) , getit( rt << 1 | 1 , m + 1 , r ); } } T[2] ; struct SAM{ int son[MAXN][27]; int par[MAXN] , len[MAXN]; int head[MAXN] , nxt[MAXN<<1] , to[MAXN<<1]; int cnt , ecnt; int s[MAXN]; void adde( int u , int v ) { to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt; } void init( ) { memset( son , 0 , sizeof son ) , memset( head , -1 , sizeof head ); cnt = lst = 1; ecnt = 0; } void addall( ) { for( int i = 2 ; i <= cnt ; ++ i ) adde( par[i] , i ); } int en[MAXN]; void ins( int x , int i ) { int cur = ++ cnt; en[cur] = i; len[cur] = len[lst] + 1; int p = lst; while( p && !son[p][x] ) son[p][x] = cur , p = par[p]; if( !p ) par[cur] = 1; else { int q = son[p][x]; if( len[q] == len[p] + 1 ) par[cur] = q; else { int cl = ++ cnt; en[cl] = en[q]; memcpy( son[cl] , son[q] , sizeof son[q] ); par[cl] = par[q]; len[cl] = len[p] + 1 , par[q] = par[cur] = cl; for( ; son[p][x] == q ; p = par[p] ) son[p][x] = cl; } } lst = cur; } void dfs( int u ) { if( head[u] == -1 ) { int t = en[u] , l = len[u] , l1 = len[par[u]]; T[0].chkmn( 1 , 1 , n , t - l1 + 1 , t , l1 ); T[1].chkmn( 1 , 1 , n , t - l + 1 , t - l1 , t ); } for( int i = head[u] ; ~i ; i = nxt[i] ) { int v = to[i]; dfs( v ); } } } S ; namespace wtf { int main() { S.init(); scanf("%s",ch + 1); n = strlen( ch + 1 ); S.init( ); for( int i = 1 ; i <= n ; ++ i ) S.ins( ch[i] - 'a' , i ); T[0].build() , T[1].build(); S.addall(); S.dfs( 1 ); memset( ans , 0x3f , sizeof ans ); T[1].getit( 1 , 1 , n ); for( int i = 1 ; i <= n ; ++ i ) { ans[i] = ans[i] - i; } T[0].getit( 1 , 1 , n ); for( int i = 1 ; i <= n ; ++ i ) printf("%d\n",ans[i] + 1); } } int main() { wtf::main(); }
|