Đếm biên (border) của mỗi tiền tố

Hướng tiếp cận

Kết hợp Z-function với mảng hiệu (difference array) để cộng dồn đóng góp của mọi khớp tiền tố lên từng tiền tố trong $O(N)$.

Nhận xét quan trọng

Với chỉ số 1-based, đặt $Z[i]$ là độ dài lớn nhất sao cho $S[i\dots i+Z[i]-1]=S[1\dots Z[i]]$.

Tiền tố $S[1\dots k]$ có biên độ dài $L$ ($1\le L<k$) khi và chỉ khi $S[k-L+1\dots k]=S[1\dots L]$. Đặt $i=k-L+1$, điều kiện trở thành $Z[i]\ge L$.

Đảo chiều: với mỗi $i\ge 2$ thỏa $Z[i]\ge 1$, vị trí $i$ đóng góp đúng $1$ biên cho mỗi tiền tố $S[1\dots k]$ với $k\in [i,i+Z[i]-1]$.

Loạt phép cộng theo đoạn này giải bằng mảng hiệu $D$, sau đó lấy tổng tiền tố.

Thuật toán

1. Tính $Z[1\dots N]$ theo thuật toán Z-function tiêu chuẩn (cửa sổ $[l,r]$, $O(N)$).
2. Mảng hiệu $D[1\dots N+1]=0$.
3. Với mỗi $i$ từ $2$ tới $N$: nếu $Z[i]\ge 1$ thì , .
4. $\mathrm{c}\mathrm{n}\mathrm{t}[k]=\mathrm{c}\mathrm{n}\mathrm{t}[k-1]+D[k]$ với $k=1,\dots ,N$.
5. In $\mathrm{c}\mathrm{n}\mathrm{t}[1],\dots ,\mathrm{c}\mathrm{n}\mathrm{t}[N]$.

Độ phức tạp

• Thời gian: $O(N)$.
• Bộ nhớ: $O(N)$.