Ký tự lặp trong hai xâu liên tiếp c++

[Tuan_Cris (tạch C++)]

link đề: https://www.spoj.com/PTIT/problems/P167PROC/
code của e: https://www.ideone.com/9PKAPQ

code của e bị quá time,các a cho e cao kiến khác để làm bài này

[tntxtnt]

code trình bày đẹp like 1 cái

truyền vector<string> vào hàm thì em truyền reference (tham chiếu), nếu ko nó copy vector cũ thành vector mới rồi mới truyền vào hàm thì chậm hơn nha :V

ví dụ

int KtraTEST(vector<string> str, int n)
//sửa thành
int KtraTEST(const vector<string>& str, int n)

//tương tự khi truyền string:
int KtraSolanlap(string str1, string str2)
//sửa thành
int KtraSolanlap(const string& str1, const string& str2)

còn hoán vị trong C++ có hàm sẵn nha em :V

do {
  // dem = xulyhoanvi(str);
} while (std::next_permutation(begin(str), end(str)));
//include thêm <algorithm> để xài next_permutation

[Grevyalres_X (Pzanitor)]

Sinh ra toàn bộ hoán vị và kiểm tra như vậy thì không hiệu quả.

Cách làm tốt hơn là sinh ra một đồ thị vô hướng với các cạnh (u,v) trọng số là số lần lặp giữa 2 chuỗi u và v . Rồi áp dụng thuật toán dp bitmask để giải bài toán Travelling Salesman Problem vào đồ thị này sẽ ra được kết quả.