Z
Bài toán
Cho một xâu S. Với mỗi vị trí i của S, gọi z[i] là giá trị lớn nhất sao cho xâu con độ dài z[i] bắt đầu tại i bằng với tiền tố độ dài z[i] của S. Nói cách khác, với mỗi i, tìm x=z[i] lớn nhất sao cho S[0..x-1] == S[i..i+x-1] (phần tử đánh số từ 0).
Độ phức tạp
O(N)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 500005
int n, z[N];
char a[N];
void make_z(char a[], int n, int F[]) {
int L = -1, R = -1;
F[0] = n;
for (int i = 1; i < n; i++) {
if (i > R) {
L = i;
R = i - 1;
while (R < n - 1 && a[R + 1] == a[R - L + 1]) R++;
F[i] = R - L + 1;
} else {
if (F[i - L] < R - i + 1)
F[i] = F[i - L];
else {
L = i;
while (R < n - 1 && a[R + 1] == a[R - L + 1]) R++;
F[i] = R - L + 1;
}
}
}
}
int main() {
gets(a);
n = strlen(a);
make_z(a, n, z);
for (int i = 0; i < n; i++)
printf("%d ", z[i]);
printf("\n");
}
Nhận xét
Hàm make_z này đã được sử dụng trong một code khác, và code đó đã được dùng để nộp cho một bài trên main.edu.pl.
Tham khảo