P4094 字符串
简化题意
给定字符串 \(s\), 每次询问给定两个字符串 \([a , b]\) 和 \([c , d]\), 求前串的所有子串和后串的最长公共前缀。
\(n \le 10 ^ 5 , m \le 10 ^ 5\)
题解
感觉其实这道题并不是特别难的，就是代码长，不折不扣的码农题。
刚开始有一个错误的想法，就是主席树维护 \(Rank\) 值查离 \(Rank_c\) 前驱后继两个值。
这个显然就是错的，因为可能匹配出的 \(LCP\) 值越过了 \(b\)，导致可能前面的长度要更优。
正解是二分答案，当钦定答案为 \(mid\) 时，显然区间为 \([a , b - mid + 1]\)。
先二分 \(Rank_y\) 上下界，使上下界为第一个和最后一个与 \(y \ LCP \ge mid\) 的位置。
主席树上查在这个区间是否有值即可。
复杂度为 \(\mathcal{O}(n \log^2 n)\)。
不卡常。
Code
CODE
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 100 ;
char s[N] ;
int n , M ;
namespace CharacterString {
namespace SuffixArray {
/*This is a algorithm in order to find suffixes and sort for them with the time complexity O(nlogn).
It supports the operation of getting the longest prefix.*/
int SA[N] , Rank[N] , m = 127 , p , Lstrk[N] , id[N] , cnt[N] , key1[N] ;
int lg[N] , ST[21][N] ;
inline void Suffix_Array() {
memset(cnt , 0 , sizeof(cnt)) ;
auto Compare = [](int x , int y , int j) {
return Lstrk[x] == Lstrk[y] && Lstrk[x + j] == Lstrk[y + j] ;
} ;
for (int i = 1 ; i <= n ; ++ i) cnt[Rank[i] = s[i]] ++ ;
for (int i = 1 ; i <= m ; ++ i) cnt[i] += cnt[i - 1] ;
for (int i = n ; i >= 1 ; -- i) SA[cnt[Rank[i]] --] = i ;
for (int j = 1 ; ; m = p , j <<= 1) {
p = 0 ;
for (int i = n ; i > n - j ; -- i) id[++ p] = i ;
for (int i = 1 ; i <= n ; ++ i) {
if (SA[i] - j > 0) {
id[++ p] = SA[i] - j ;
}
}
memset(cnt , 0 , sizeof(cnt)) ;
for (int i = 1 ; i <= n ; ++ i) {
++ cnt[key1[i] = Rank[id[i]]] ;
}
for (int i = 1 ; i <= m ; ++ i) cnt[i] += cnt[i - 1] ;
for (int i = n ; i >= 1 ; -- i) {
SA[cnt[key1[i]] --] = id[i] ;
}
memcpy(Lstrk , Rank , sizeof(Rank)) ; p = 0 ;
for (int i = 1 ; i <= n ; ++ i) {
Rank[SA[i]] = Compare(SA[i] , SA[i - 1] , j) ? p : ++ p ;
}
if (p == n) break ;
}
}
inline int MinST(int l , int r) {
int k = lg[r - l + 1] ;
return min(ST[k][l] , ST[k][r - (1 << k) + 1]) ;
}
inline int LCP(int l , int r) {
if (l == r) return n - l + 1 ;
if (Rank[l] > Rank[r]) swap(l , r) ;
return MinST(Rank[l] + 1 , Rank[r]) ;
}
inline void GetHeight() {
for (int i = 2 ; i <= n ; ++ i) lg[i] = lg[i >> 1] + 1 ;
for (int i = 1 , k = 0 ; i <= n ; ++ i) {
if (!Rank[i]) continue ;
if (k) k -- ;
while (s[i + k] == s[SA[Rank[i] - 1] + k]) ++ k ;
ST[0][Rank[i]] = k ;
}
for (int j = 1 ; j <= lg[n] ; ++ j) {
for (int i = 1 ; i <= n - (1 << j) + 1 ; ++ i) {
ST[j][i] = min(ST[j - 1][i] , ST[j - 1][i + (1 << (j - 1))]) ;
}
}
}
}
} using namespace CharacterString ;
using namespace SuffixArray ;
namespace Chairman_Tree {
#define lson(x) t[x].son[0]
#define rson(x) t[x].son[1]
#define data(x) t[x].data
#define mid ((l + r) >> 1)
struct Node {
int son[2] , data ;
} t[N * 200] ; int root[N] , numbol ;
void updata(int &now , int id , int l , int r , int x) {
t[now = ++ numbol] = t[id] ;
if (l == r) return t[now].data ++ , void() ;
if (x <= mid) updata(lson(now) , lson(id) , l , mid , x) ;
else updata(rson(now) , rson(id) , mid + 1 , r , x) ;
t[now].data = t[lson(now)].data + t[rson(now)].data ;
}
bool check(int fir , int sec , int l , int r , int x , int y) {
if (x <= l && r <= y) return (data(fir) - data(sec) != 0) ;
bool flag = 0 ;
if (x <= mid) flag |= check(lson(fir) , lson(sec) , l , mid , x , y) ;
if (y > mid) flag |= check(rson(fir) , rson(sec) , mid + 1 , r , x , y) ;
return flag ;
}
#undef mid
} using namespace Chairman_Tree ;
pair <int , int> Find(int now , int x) {
int left = 1 , right = now - 1 , ans1 = now , ans2 = now ;
while (left <= right) {
int mid = (left + right) >> 1 ;
if (LCP(SA[mid] , SA[now]) >= x) {
ans1 = mid ;
right = mid - 1 ;
} else left = mid + 1 ;
}
left = now + 1 , right = n ;
while (left <= right) {
int mid = (left + right) >> 1 ;
if (LCP(SA[mid] , SA[now]) >= x) {
left = mid + 1 ;
ans2 = mid ;
} else right = mid - 1 ;
}
return make_pair(ans1 , ans2) ;
}
signed main() {
// freopen("1.in" , "r" , stdin) ;
// freopen("1.out" , "w" , stdout) ;
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
cin >> n >> M ;
for (int i = 1 ; i <= n ; ++ i) cin >> s[i] ;
Suffix_Array() ; GetHeight() ;
int ans = 0 ; pair <int , int> mp ;
for (int i = 1 ; i <= n ; ++ i) updata(root[i] , root[i - 1] , 1 , n , Rank[i]) ;
for (int i = 1 , w , x , y , z ; i <= M ; ++ i) {
cin >> w >> x >> y >> z ; ans = 0 ;
int left = 1 , right = min(x - w + 1 , z - y + 1) ;
while (left <= right) {
int mid = (left + right) >> 1 ;
mp = Find(Rank[y] , mid) ; int L = mp.first , R = mp.second ;
if (check(root[x - mid + 1] , root[w - 1] , 1 , n , L , R)) {
left = mid + 1 ; ans = mid ;
} else right = mid - 1 ;
}
cout << ans << '\n' ;
}
}