CF700E Cool Slogans

以前做的,没发博客。

如果两个串的 endpos 等价类相同,显然把任意一个放进 sis_i 里面是一样的效果。

于是我们可以建出 SAMfail 树,考虑做 dp[u]dp[u] 表示当前在树上的 uu 节点,同时我们最后一次选择的是这个点上的最长串,最多可以选出的序列长度。

显然,我们选择一个深度更大的位置比选择一个深度更小的位置作为序列的上一个位置好。因为深度更小的位置一定在深度更大的位置的所有 endpos 中出现过。所以我们可以考虑找到最深的一个位置,满足这个位置在当前串中出现过至少两次。

我们可以进行可持久化线段树合并,然后倍增来跳这个位置。如果一个位置 vv 满足,即意味着在 rt[v]rt[v] 的线段树里面在 [rlen[u]+len[v],r1][r-len[u]+len[v],r-1] 之间有过值,也就是有过 endpos

直接进行线段树区间查询即可。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 800006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];
char ch[MAXN];

struct SAM {
	int son[MAXN][26] , par[MAXN] , len[MAXN] , cnt , lst;
	void init( ) {
		lst = cnt = 1;
	}
	int rt[MAXN] , cn , ls[MAXN * 10] , rs[MAXN * 10] , T[MAXN * 10];
	void add( int& rt , int l , int r , int p ) {
		if( !rt ) rt = ++ cn;
		++ T[rt];
		if( l == r ) return;
		int m = l + r >> 1;
		if( p <= m ) add( ls[rt] , l , m , p );
		else add( rs[rt] , m + 1 , r , p );
	}
	vi G[MAXN];
	void addall( ) {
		for( int i = 2 ; i <= cnt ; ++ i ) G[par[i]].pb( i );
	}
	void ins( int x , int i ) {
		int cur = ++ cnt , p = lst;
		len[cur] = len[lst] + 1;
		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 ct = ++ cnt;
				len[ct] = len[p] + 1 , par[ct] = par[q];
				memcpy( son[ct] , son[q] , sizeof son[ct] );
				par[q] = par[cur] = ct;
				for( ; son[p][x] == q ; p = par[p] ) son[p][x] = ct;
			}
		}
		lst = cur;
		add( rt[cur] , 1 , n , i );
	}
	int merge( int u , int v , int l , int r ) {
		if( !u || !v ) return u ^ v;
		int cur = ++ cn , m = l + r >> 1;
		T[cur] = T[u] + T[v];
		if( l == r ) return cur;
		ls[cur] = merge( ls[u] , ls[v] , l , m ) , rs[cur] = merge( rs[u] , rs[v] , m + 1 , r );
		return cur;
	}
	int que( int rt , int l , int r , int L , int R ) {
		if( !rt ) return 0;
		if( L <= l && R >= r ) return 1;
		int m = l + r >> 1 , ans = 0;
		if( L <= m ) ans |= que( ls[rt] , l , m , L , R );
		if( R > m ) ans |= que( rs[rt] , m + 1 , r , L , R );
		return ans;
	}
	int yusland( int rt , int l , int r ) {
		if( l == r ) return l;
		int m = l + r >> 1;
		if( rs[rt] ) return yusland( rs[rt] , m + 1 , r );
		if( ls[rt] ) return yusland( ls[rt] , l , m );
	}
	int g[MAXN][20];
	void dfs( int u ) {
		for( int v : G[u] ) {
			g[v][0] = u;
			for( int k = 1 ; k < 19 ; ++ k ) if( g[g[v][k-1]][k-1] ) g[v][k] = g[g[v][k-1]][k-1]; else break;
			dfs( v ) , rt[u] = merge( rt[u] , rt[v] , 1 , n );
		}
	}
	int jump( int u , int l , int r ) {
		for( int k = 18 ; k >= 0 ; -- k ) {
			int v = g[u][k];
			if( !v || ( l + len[v] - 1 <= r - 1 && que( rt[v] , 1 , n , l + len[v] - 1 , r - 1 ) ) ) continue;
			u = g[u][k];
		}
		return par[u];
	}
	int dp[MAXN] , ans = 0;
	void sol( int u ) {
		if( u != 1 ) {
			int ps = yusland( rt[u] , 1 , n ) , v = jump( u , ps - len[u] + 1 , ps );
			dp[u] = dp[v] + 1;
		}
		ans = max( ans , dp[u] );
		for( int v : G[u] ) 
			sol( v );
	}
	void fuck( ) {
		for( int i = 2 ; i <= cnt ; ++ i ) cout << i << ' ' << dp[i] << endl;
	}
} S ;

void solve() {
	cin >> n;
	scanf("%s",ch + 1);
	S.init();
	rep( i , 1 , n ) S.ins( ch[i] - 'a' , i );
	S.addall( );
	S.dfs( 1 );
	S.sol( 1 );
	cout << S.ans << endl;
//	S.fuck();
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}

\