Tìm các xâu con khác nhau trong xâu mẹ

[intwest]

Cho mình hỏi thuật toán bài này với ạ, mình đếm nó bị trùng xâu mất rồi

Ví dụ: S = ‘ABAB’ ta có các xâu con liên tiếp khác nhau là: ‘A’, ‘B’, ‘AB’, ‘BA’, ‘ABA’, ‘BAB’, ‘ABAB’. Suy ra số lượng xâu con liên tiếp khác nhau là 7.

Input:

• Một xâu S.

Output:

• Số lượng xâu con liên tiếp khác nhau.

Ví dụ:

Input:
ABAB

Output:
7

[Tung_Thanh1 (Tùng Thanh)]

xauconkhacnhau - Pastebin.com
Dùng set là oke b

[intwest]

hic hic
chỉ mình set là gì với, nó lạ quá điiiiii

[ongchamchi (Ong Chăm Chỉ)]

Dùng 2 vòng for lồng nhau và 1 đối tượng Set.

var n = chuỗi.length;

for(var i = 1; i <= n ; i++){
      for(var j = 0; j <= n - 1; j ++){
            if( j + i <= n)
            set.add(chuỗi.subString( cắt từ vị trí j, lấy số lượng i);
     }
}

Set là cấu trúc dữ liệu dạng list, khi add phần tử mới X, nếu X chưa có thì thêm vào, có rồi sẽ bỏ qua. Nên list không bao giờ có phần tử trùng.

[rogp10]

Chuỗi dài hơn 5000 kí tự thì phải dùng Suffix Trie vì lưu hết bằng ấy chuỗi con là hết mem, trong khi 1 node của Suffix Trie ứng với 1 chuỗi con.

[noname00 (HK boy)]

@ongchamchi

Set là cấu trúc dữ liệu dạng list

std::set được build dưới dạng self-balanced binary search tree (thường là red-black tree), không phải list.

Vì bạn @intwest không ghi giới hạn n (= độ dài xâu) là bao nhiêu nên mình chỉ có thể nói rằng cách của anh @rogp10 phù hợp với n lớn, còn cách sinh ra mọi xâu con rồi nhét vào set thì chỉ phù hợp với n nhỏ (n tầm 500 đổ lại, vì cách này tốn O(n^3 log n) thời gian và O(n^3) memory).