Có thể đếm số lượng các phân đoạn riêng biệt trong một chuỗi trong O (n) không?

Question

Cho một chuỗi s chiều dài n, có thể đếm số lượng các phân đoạn riêng biệt trong s trong O (n) không?

Ví dụ

Input: abb

Output: 5 ('abb', 'ab', 'bb', 'a', 'b')

Tôi đã làm một số nghiên cứu, nhưng tôi dường như không thể tìm thấy một thuật toán giải quyết vấn đề này trong đó một cách hiệu quả. Tôi biết một cách tiếp cận O (n^2) là có thể, nhưng có một thuật toán hiệu quả hơn?

Tôi không cần lấy từng bản chất, chỉ là tổng số các phần tử khác nhau (trong trường hợp nó tạo sự khác biệt).

Answer 1

Bạn có thể sử dụng thuật toán Ukkonen để xây dựng một cây hậu tố trong thời gian tuyến tính:

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

Số chuỗi con của s là sau đó số lượng tiền tố của chuỗi trong Trie, mà bạn có thể tính toán đơn giản trong thời gian tuyến tính. Nó chỉ là tổng số ký tự trong tất cả các nút.

Ví dụ, ví dụ bạn tạo ra một cây hậu tố như:

  /\     
      b a 
      | b 
      b b 

5 nhân vật trong cây, vì vậy 5 chuỗi con. Mỗi chuỗi duy nhất là một đường dẫn từ gốc kết thúc sau một chữ cái khác nhau: abb, ab, a, bb, b. Vì vậy, số lượng chuỗi là số chữ cái trong cây.

Chính xác hơn:

• Mỗi chuỗi con là tiền tố của một số hậu tố của chuỗi;
• Tất cả các hậu tố đều có trong bộ ba;
• Vì vậy, có một sự tương ứng 1-1 giữa các chất nền và đường dẫn qua trie (theo định nghĩa của trie); và
• Có một sự tương ứng 1-1 giữa các chữ cái trong cây và không có sản phẩm nào con đường, bởi vì:
  • mỗi đường dẫn không trống riêng biệt kết thúc ở một vị trí riêng biệt sau khi lá thư cuối cùng của nó; và
  • đường dẫn đến các vị trí sau mỗi chữ cái là duy nhất

Chú ý đối với những người đang tự hỏi làm thế nào nó có thể là có thể xây dựng một cây có chứa ký tự O (N^2) trong thời gian O (N) thời gian:

Có một mẹo để trình bày cây hậu tố. Thay vì lưu trữ các chuỗi thực tế trong các nút của cây, bạn chỉ lưu trữ các con trỏ vào chuỗi ký tự, vì vậy nút chứa "abb" không có "abb", nó có (0,3) - 2 số nguyên trên mỗi nút, bất kể chuỗi trong mỗi nút là bao lâu và cây hậu tố có các nút O (N).

Answer 2

Xây dựng LCP array và trừ tổng số của nó khỏi số lượng phần tử (n (n + 1)/2).