Editorial for Bedao Regular Contest 13 - DELCHAR


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Khi nào thì ~t_i = t_j~?

Dựa vào hình vẽ trên, ta thấy:

  • Với ~1 \le p < i~, ta có: ~t_i[p] = t_j[p] = s[p]~.
  • Với ~i \le k < j~, ta có: ~t_i[p] = s[p + 1]~, ~t_j[p] = s[p]~.
  • Với ~j \le p < n~, ta có: ~t_i[p] = t_j[p] = s[p + 1]~.

Vì vậy, ~t_i = t_j~ khi và chỉ khi ~s[i] = s[i + 1] = \ldots = s[j]~.

Để đếm số cặp số ~(i, j)~ thỏa điều kiện này, có rất nhiều cách khác nhau: ta có thể tách xâu ~s~ ban đầu thành các đoạn liên tiếp có ký tự giống nhau. Với một đoạn ký tự độ dài ~k~, ta sẽ tìm được ~\frac{k(k - 1)}{2}~ cặp số ~(i, j)~ thỏa mãn.

Độ phức tạp: ~O(|s|)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.