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|)~.