Tách chuỗi con trong C++

#1

Mình chào mọi người ạ, chuyện là mình có 1 bài tập về tách chuỗi nhưng hơi phức tạp và mình chưa nghĩ ra cách nên đành nhờ mọi người giúp. Bài tập cho một chuỗi kí tự ví dụ aabcdabfecabklm, từ chuỗi mẹ này, có thể ghép đc tối đa bao nhiêu chuỗi con “abc”. Mình có ý tưởng là từ chuỗi mẹ mình chạy 1 vòng lặp chỉ lấy các chữ a,b,c lưu vào 1 chuỗi con substr, tức là lúc này substr=“aabcabca” và lúc này đếm số chuỗi abc có thể ghép đc từ từng kí tự con trong substr, đáp án là 5, vđề là từ lúc đếm số chuỗi abc này mình kh biết phải viết chương trình như thế nào. Mong mng giúp đỡ.

#2

đề bài còn chưa rõ ràng thì ai mà giúp được gì

2 Likes
#3

Không đảo thứ tự của các kí tự phải không?
Đây là 5 kết quả thu được:

aabcabca
^ ^^
aabcabca
 ^^^
aabcabca
^    ^^
aabcabca
 ^   ^^
aabcabca
    ^^^
3 Likes
#4

hình như có tới 7 lận mà :V :V

aabcabca
^ ^^
aabcabca
^ ^   ^    // mới
aabcabca
 ^^^
aabcabca
 ^^   ^    // mới
aabcabca
^    ^^
aabcabca
 ^   ^^
aabcabca
    ^^^

chỉnh sửa thuật toán longest common subsequence là được :V đếm thêm số lượng subsequence có cùng độ dài. O(mn) nhưng vì m có độ dài là 3 nên còn lại O(n), ko cần trích abc cũng được :V trích thì chạy lẹ hơn tí nếu chuỗi có ít a,b,c còn chuỗi chỉ chứa a,b,c ko thì lại mất thời gian trích xuất vô ích :V

5 Likes
#5

Oh đúng rồi có 7 cái mình đếm thiếu á. Mình hiểu cách làm r cảm ơn bạn nhé!

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?