Thuật toán tạo và tìm xâu đối xứng

phamthanhnhan · 23/7/16

Thế nào là xâu đối xứng?
- Xâu đối xứng là khi sau đó và một xâu viết ngược lại của xâu đó bằng nhau
- VD : RADAR, TOT, GEDFDED, ... là các xâu đối xứng
- Xâu chuỗi 'TOMATO' không phải là xâu đối xứng (TOMATO <> OTMAOT)
- Ta có thể tạo được sau đối xứng với chuỗi tomato nếu thêm vào các kí tự hợp lí
- VD: TOMATOOTMAOT (thêm OTMAOT vào phía sau), hoặc TOTMAMTOT (thêm T , M ,T vào các vị trí thích hợp)

Đề bài: Hãy viết một chương trình để nhận biết xâu có phải là đối xứng hay không, nếu không thì cần thêm vào ít nhất bao nhiêu kí tự để xâu thành xâu đối xứng

Em không suy nghĩ ra được giải thuật nào tối ưu hết ngoài vét cạn, nhưng như vậy rất tốn thời gian trong khi chuỗi lại có tối 255 kí tự, các bác có ai có thuật toán hay mong được chỉ giáo ạ.

phamthanhnhan · 23/7/16

có thớt nào giúp em với ạ, em vô cùng biết ơn

tengiday · 24/7/16

Mình nghĩ bài này có thể giải bằng quy hoạch động. Đây là ý tưởng của mình.
F[i, j] = Số ký tự ít nhất cần thêm vào xâu S[i..j] để nó thành 1 xâu đối xứng.
Ta có công thức như sau:
F[i, i] = 0.
F[i, j] = F[i + 1, j - 1] nếu S = S[j].
F[i, j] = min(F[i + 1, j], F[i, j - 1]) + 1 nếu S <> S[j].

Kết quả sẽ được lưu ở F[1, n], với n là chiều dài của chuỗi S.

phamthanhnhan · 24/7/16

tengiday:
Mình nghĩ bài này có thể giải bằng quy hoạch động. Đây là ý tưởng của mình.
F[i, j] = Số ký tự ít nhất cần thêm vào xâu S[i..j] để nó thành 1 xâu đối xứng.
Ta có công thức như sau:
F[i, i] = 0.
F[i, j] = F[i + 1, j - 1] nếu S = S[j].
F[i, j] = min(F[i + 1, j], F[i, j - 1]) + 1 nếu S <> S[j].

Kết quả sẽ được lưu ở F[1, n], với n là chiều dài của chuỗi S.

em cảm ơn nhiều lắm, nhưng mà em chưa hiểu rõ lắm, các giải thích thêm tí cho em tí nha, tại sao là mảng 2 chiều vậy bác ?

tengiday · 24/7/16

Đấy chỉ là ý tưởng của mình thôi vì mình đang bận, ko test kĩ đc.
- F[i,i] = 0: cái này chắc dễ hiểu. Chuỗi có 1 ký tự luôn là đối xứng.
- Nếu S = S[j] (i < j), thì chúng ta có thể mở rộng chuỗi từ S[i + 1 .. j - 1] mà chuỗi vẫn là đối xứng.
- Nếu S <> S[j] (i < j), thì mình nghĩ có 2 trường hợp: mở rộng từ S[i + 1 .. j] hoặc S[i .. j - 1]; còn mình + 1 là do sự khác nhau giữa S và S[j].

Nếu chiều dài tối đa của S là 255 thì có thể dùng mảng 2 chiều này được (có thể dùng array of byte), nếu thiếu bộ nhớ thì cấp phát động thêm tí xíu chắc là chạy được. Nếu không thì bạn có thể dùng 3 mảng 1 chiềuu để lưu trữ.
- Muốn in kết quả cụ thể ký tự nào thì khó hơn. Mình nghĩ chắc là phải lưu lại mảng dấu tại mỗi bước điền vào F. Khi đó phải cấp phát động mới đủ bộ nhớ. Đương nhiên, nếu dùng Free Pascal sẽ không bị sao cả.

Bạn hiểu ý tưởng rồi góp ý cho mình.

phamthanhnhan · 24/7/16

em dùng pascal ạ, nên không cấp phát động

còn việc dùng mảng để lưu char thì cũng đang xem xét, tuy vậy cũng có chút khó khăn ngay cả nhập từ bàn phím hay từ file ạ
p/s: em đang test giải thật của bác, thanks bác đã hỗ trợ ạ

tengiday · 24/7/16

phamthanhnhan:
em dùng pascal ạ, nên không cấp phát động
còn việc dùng mảng để lưu char thì cũng đang xem xét, tuy vậy cũng có chút khó khăn ngay cả nhập từ bàn phím hay từ file ạ
p/s: em đang test giải thật của bác, thanks bác đã hỗ trợ ạ

Pascal từ năm 1989 có cấp phát động mà. Bạn thử nhé:

Mã:

type arrayChar = array[0..255] of char;
var a : ^arrayChar;
begin
    new(a);
    a^[0] := '1';
    dispose(a);
end.

phamthanhnhan · 24/7/16

tengiday:
Đấy chỉ là ý tưởng của mình thôi vì mình đang bận, ko test kĩ đc.
- F[i,i] = 0: cái này chắc dễ hiểu. Chuỗi có 1 ký tự luôn là đối xứng.
- Nếu S = S[j] (i < j), thì chúng ta có thể mở rộng chuỗi từ S[i + 1 .. j - 1] mà chuỗi vẫn là đối xứng.
- Nếu S <> S[j] (i < j), thì mình nghĩ có 2 trường hợp: mở rộng từ S[i + 1 .. j] hoặc S[i .. j - 1]; còn mình + 1 là do sự khác nhau giữa S và S[j].

Nếu chiều dài tối đa của S là 255 thì có thể dùng mảng 2 chiều này được (có thể dùng array of byte), nếu thiếu bộ nhớ thì cấp phát động thêm tí xíu chắc là chạy được. Nếu không thì bạn có thể dùng 3 mảng 1 chiềuu để lưu trữ.
- Muốn in kết quả cụ thể ký tự nào thì khó hơn. Mình nghĩ chắc là phải lưu lại mảng dấu tại mỗi bước điền vào F. Khi đó phải cấp phát động mới đủ bộ nhớ. Đương nhiên, nếu dùng Free Pascal sẽ không bị sao cả.

Bạn hiểu ý tưởng rồi góp ý cho mình.

bác cho em hỏi là I, J chạy vòng lặp như thế nào ạ, và lúc khởi tạo thì i=1 hay i= length(s) div 2 ạ ?

tengiday · 25/7/16

phamthanhnhan:
bác cho em hỏi là I, J chạy vòng lặp như thế nào ạ, và lúc khởi tạo thì i=1 hay i= length(s) div 2 ạ ?

- Đầu tiên bạn nên khởi tạo F[i,i] = 0.
- Sau đó xử lý trường hợp chuỗi S[i..i+1] (tức là chuỗi có chiều dài là 2).
- Tiếp theo, để điền mảng F, bạn cần chạy theo "chiều dài của chuỗi bắt đầu từ 3" và "vị trí bắt đầu". Ví dụ code như thế này:

Mã:

for len := 3 to n do   // chiều dài của chuỗi cần xét, chuỗi có chiều dài từ 3 ký tự đến toàn bộ chuỗi
   for i := 0 to n - len     // vị trí bắt đầu xét
      F[i, i + len - 1] .....   // xét từ vị trí S[i], chuỗi con có chiều dài 'len'.

Cuối cùng, kết quả sẽ nằm ở F[0, n-1].
Ý tưởng là như thế, index của mình có thể bị lệch vì mình chuyển từ C++ sang, bạn kiểm tra lại giúp mình nhé. Để có thể thấy rõ hơn, tại mỗi bước 'len', chúng ta có thể in mảng F ra.

PS: Một cách khác là nghĩ theo hướng xâu con chung có độ dài lớn nhất, gọi là K, như vậy kết quả là N - K. Cách làm này cũng sẽ dùng quy hoạch động.

phamthanhnhan · 25/7/16

mình đã test nhưng kết quả không như mong muốn, có thể mình sai ở chỗ nào đó
tiện thể bác gửi cho em code của C++ được không ạ? Em cũng hiểu code c++

tengiday · 25/7/16

Mình viết nó như thế này:

Mã:

short palindrome(char * s, short len) {
    if (len == 1) return 0;
    short ** F = new short*[len];
    for (short i = 0; i < len; ++i) {
        F[i] = new short[len];
        F[i][i] = 0;
    }

    for (short i = 0; i < len - 1; ++i)
        if (s[i] == s[i + 1])
            F[i][i + 1] = 0;
        else
            F[i][i + 1] = 1;
    for (short i = 3; i <= len; ++i)
        for (short j = 0; j <= len - i; ++j)
            if (s[j] == s[j + i - 1])
                F[j][j + i - 1] = F[j + 1][j + i - 2];
            else
                F[j][j + i - 1] = min(F[j + 1][j + i - 1], F[j][j + i - 2]) + 1;
     
    short result = F[0][len - 1];

    for (short i = 0; i < len; ++i)
        delete[] F[i];
    delete[] F;
    return result;
}

Còn đây là test của mình. Có 62 ký tự khác nhau được lặp lại 80 lần. Kết quả là 4801.

Mã:

char * s = new char[4960];
for (short i = 0; i < 80; ++i)
   for (short j = 33; j < 33 + 62; ++j)
    s[i * 62 + j - 33] = char(j);
printf("\n%d\n", palindrome(s, 4960));
delete[] s;

Về tốc độ thì khá là tối ưu O(n^2), còn về memory thì vẫn chưa. Tối ưu về space phải là O

, trong khi của mình tới O(n^2) lận.

phamthanhnhan · 25/7/16

em đã tìm ra thuật toán rồi ạ, thanks chủ thớt đã gợi ý, em dùng hai cái repeat until (trong c++ là do while) riêng biệt là xong ạ

Thuật toán tạo và tìm xâu đối xứng

phamthanhnhan

(｡◕‿‿◕｡) づ

tengiday

Happy life

phamthanhnhan

(｡◕‿‿◕｡) づ

tengiday

Happy life

phamthanhnhan

(｡◕‿‿◕｡) づ

tengiday

Happy life

phamthanhnhan

(｡◕‿‿◕｡) づ

tengiday

Happy life

phamthanhnhan

(｡◕‿‿◕｡) づ

tengiday

Happy life

phamthanhnhan

(｡◕‿‿◕｡) づ

Bài viết mới nhất

Bài viết đang hot

Thống kê

Bài viết được quan tâm nhiều