Chuỗi ký tự nâng cao
Băm chuỗi
Băm đa thức
\(f(s)=\sum^l_{r=1}s_i\times b^{i-1}\pmod M\)。
Băm ma trận
Phù hợp cho việc băm tập hợp chuỗi.
Nếu dùng băm đa thức, tập hợp chuỗi \(\{ab,bd\}\) và \(\{ad,bd\}\) sẽ có cùng giá trị băm.
Ta biểu diễn mỗi ký tự thành một ma trận \(2\times 2\). Với chuỗi giống nhau thì nhân ma trận, khác nhau thì cộng ma trận. Vì phép nhân ma trận thường không giao hoán nên giá trị băm thường khác nhau.
Ví dụ
P3370
Mẫu băm đa thức.
Ứng dụng tiêu biểu
Cho chuỗi \(S\) và \(q\) truy vấn, mỗi lần truy vấn hai vị trí \(l_1,l_2\) tìm chiều dài tiền tố chung dài nhất, với \(|S|,q\leq3\times10^5\).
Giải pháp đúng: Dùng \(Hash\) và nhị phân.
CF 1017E
UOJ552
Tương đương với cho hai tập chuỗi có thể lặp lại, tìm chuỗi ngắn nhất, có thứ tự từ điển nhỏ nhất.
Rõ ràng thỏa mãn tính chất của băm ma trận.
Mỗi đỉnh lưu giá trị băm bắt đầu từ nó.
Thuật toán KMP
Một thuật toán khớp chuỗi đơn giản.
Hàm tiền tố
Định nghĩa
Gọi \(nxt_i\) là độ dài tiền tố lớn nhất mà trùng với hậu tố bắt đầu tại vị trí \(i\).
Ví dụ, mảng \(nxt\) của chuỗi abcabcd là \(\{0,0,0,1,2,3,0\}\).
Cài đặt
for(int i=1,j=0;i<s2.length();i++){
while(j && s2[i] != s2[j]){// Không khớp hoặc đến đầu, quay lại vị trí trước đó.
j = nxt[j];
}
if(s2[i] == s2[j]){// Khớp thì tiến thêm một bước.
j ++;
}
nxt[i+1] = j;
}
Thuật toán KMP
Tình huống áp dụng
Giải bài toán khớp chuỗi \(P\) trong chuỗi \(T\).
Các bước
- Tính hàm tiền tố cho chuỗi \(P\);
- Sử dụng mảng \(nxt\) để khớp trong chuỗi \(T\).
Cài đặt
for(int i=1;j=0;i<=s2.length();i++){
while(j && s2[i] != s2[j]){
j = nxt[j];
}
if(s1[i] == s2[j]){
j ++;
}
nxt[i+1] = j;
}
for(int i=0,j=0;i<s1.length();i++){
while(j && s1[i] != s2[j]){
j = nxt[j];
}
if(s1[i] == s2[j]){
j ++;
}
if(j == s2.lenght()){
ans[++cnt] = i-s2.lengyh()+2;
}
}
Ví dụ
NOI2014 动物园 (P2375)
Thuật toán KMP mở rộng (Hàm Z)
Tình huống ứng dụng
Từ vị trí nào đó trong chuỗi \(S\), tối đa có thể khớp bao nhiêu ký tự của chuỗi \(P\).
Hàm Z
Định nghĩa
Với chuỗi độ dài \(N\) \(S\), \(z_i\) là độ dài tiền tố chung dài nhất giữa chuỗi \(S\) và \(S_{i:N}\).
Ví dụ, chuỗi \(S=aaabaaabc\) tương ứng với \(z=\{9,2,1,0,4,2,1,0\}\).
Thuật toán đơn giản
Tìm kiếm trực tiếp
Duyệt từng vị trí, kiểm tra trực tiếp. Độ phức tạp thời gian \(O(N^2)\).
Dùng Hash + nhị phân
Dùng \(Hash\) để tối ưu so sánh. Độ phức tạp \(O(n\log m+m)\).
Hộp Z
Định nghĩa
Hộp Z là đoạn \([l,r]\) của chuỗi \(S\) sao cho đoạn này là tiền tố của \(S\) và \(r\) đạt giá trị lớn nhất.
Ví dụ với chuỗi \(S=aaabaaabc\), đoạn \([4,7]\) rõ ràng là tiền tố.
Do đó ta có thể suy ra \(z_i\) của đoạn \([5,7]\) từ đoạn \([1,3]\).
Cài đặt
for(int i=2,l=0,r=0;i<=n;i++){
if(i <= r){// Trong hộp Z;
z[i] = min(z[i-l+1],r-i+1);
// z[i] có thể lấy từ z[i-l+1];
// nhưng độ dài không vượt quá r-i+1;
}
while(s[1+z[i]] == s[i+z[i]]){
// Kiểm tra bước tiếp theo
z[i] ++;
}
if(i+z[i]-1 > r){
// Nếu điểm phải mới hơn hộp hiện tại, cập nhật hộp mới;
l = i;
r = i+z[i]-1;
}
}
Vì điểm phải \(r\) chỉ di chuyển tối đa \(n\) bước nên độ phức tạp là \(O(N)\).
Ví dụ
P5410
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e7+5;
char a[N],b[N];
int n,m;
int z[N],p[N];
void get_z(char *b){
z[1] = n;
for(int i=2,l=0,r=0;i<=n;i++){
if(i <= r){// Trong hộp Z;
z[i] = min(z[i-l+1],r-i+1);
// z[i] có thể lấy từ z[i-l+1];
// nhưng độ dài không vượt quá r-i+1;
}
while(b[1+z[i]] == b[i+z[i]]){
// Kiểm tra bước tiếp theo
z[i] ++;
}
if(i+z[i]-1 > r){
// Nếu điểm phải mới hơn hộp hiện tại, cập nhật hộp mới;
l = i;
r = i+z[i]-1;
}
}
ll ans = 0;
for(int i=1;i<=n;i++){
// cout<<z[i]<<' ';
ans ^= (ll)i*((ll)z[i]+1ll);
}
printf("%lld\n",ans);
}
void exkmp(char *a,int m,char *b,int n){
for(int i=1,l=0,r=0;i<=m;i++){
if(i <= r){
p[i] = min(z[i-l+1],r-i+1);
}
while(i+p[i] <= m && a[i+p[i]] == b[p[i]+1]){
p[i] ++;
}
if(i+p[i]-1 > r){
l = i;
r = i+p[i]-1;
}
}
ll ans = 0;
for(int i=1;i<=m;i++){
ans ^= (ll)i*((ll)p[i]+1ll);
}
printf("%lld",ans);
}
int main(){
scanf("%s%s",a+1,b+1);
m = strlen(a+1);
n = strlen(b+1);
get_z(b);
exkmp(a,m,b,n);
}
Câu hỏi thứ hai tương ứng với nối chuỗi \(a\) và \(b\), sau đó tính \(z_i\) cho \(strlen(a)\) phần tử đầu tiên.
Manacher
Định nghĩa
- Chuỗi đối xứng: Chuỗi đọc từ trái sang phải và ngược lại đều giống nhau, tức là \(\forall s_i=s_{N-i}\).
- Chuỗi con đối xứng: Là chuỗi con vừa đối xứng vừa là một phần của chuỗi.
- Chuỗi lẻ: Chuỗi có độ dài lẻ.
- Chuỗi chẵn: Chuỗi có độ dài chẵn.
Manacher thường dùng để tìm chiều dài chuỗi con đối xứng dài nhất trong chuỗi \(S\).
Thuật toán đơn giản
Thử tất cả
Duyệt từng cặp đầu cuối và kiểm tra xem có phải chuỗi đối xứng không. Độ phức tạp \(O(N^3)\).
Có thể tối ưu bằng cách duyệt từng vị trí trung tâm rồi mở rộng hai bên. Độ phức tạp \(O(N^2)\).
Dùng Hash + nhị phân
Duyệt từng vị trí, nhị phân độ dài chuỗi, dùng Hash kiểm tra đối xứng. Độ phức tạp \(O(n\log n)\).
Các bước cài đặt
Giả sử \(S=aaba\).
Chỉnh sửa chuỗi
Chèn một ký tự đặc biệt giữa các ký tự, ví dụ #.
Khi đó \(S=\#a\#a\#b\#a\#\), mọi chuỗi con đối xứng đều là đối xứng lẻ, thuận tiện cho xử lý tiếp theo.
Để dễ cài đặt, thường thêm một ký tự khác vào đầu chuỗi, ví dụ $.
Khi đó \(S\) trở thành $#a#a#b#a#.
Hộp tăng tốc
Tương tự như KMP mở rộng, Manacher cũng có khái niệm "hộp".
Chúng ta duy trì hộp đối xứng có điểm phải xa nhất. Sử dụng trạng thái trước đó để tăng tốc tính toán.
Tương tự, bên trong hộp dùng chuyển tiếp nhanh, bên ngoài duyệt trực tiếp.