# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Mình có 1 số bài pascal 11 mong các bạn giúp đỡ

## dinhmailam8

Bài 1: Viết chương trình in ra tần số xuất hiện của các số trong 1 dãy số nguyên. Dữ liệu lấy từ tệp dulieu.inp, dòng thứ nhất ghi N số nguyên a1, a2,..,an. Kết quả ghi vào tệp dulieu.out.
Bài 2: Viết chương trình xét xem có hay không một xâu X sao cho xâu S là xâu được ghép liên tục từ xâu X.
Bài 3: Cho 2 xâu S1, S2. Thông báo độ dài của xâu S1, S2. Hãy xét xem S1 xuất hiện bao nhiêu lần trong S2 và xuất hiện ở những vị trí nào ?
Bài 4: Viết chương trình đưa ra tần số xuất hiện của mỗi kí tự trong 1 xâu cho trước.
Bài 5: Thông báo xem xâu S2 có thể tạo ra nhờ xóa đi một số kí tự từ xâu S1 hay không.
Bài 6: Kiểm tra 1 xâu có phải là xâu đối xứng hay không ?
Bài 7: Tìm độ dài xâu con đối xứng dài nhất trong 1 xâu kí tự bất kỳ. Ghi ra xâu đó.
_(Sử dụng kiến thức 11 thôi nha)_
​

----------


## nguyentruong17

Đêm rùi, mình chỉ viết ý tưởng thôi nha, bạn cố dùng kiến thức của mình để biến thành chương trình nha:
Bài 1: dùng 2 mảng với ý nghĩa: 
_ Mảng A : A_ chứa số cần đếm số lần xuất hiện.
_ Mảng B: B Chứa tần số của A.
Bạn đọc số vào, nếu số đó chưa có ở mảng A thì tăng i, gán A = số đó, tăng B.
Nếu số đó có rồi thì tìm vị trí i để A= số đó, tăng B.
Kết quả in ra thì có mảng B rồi, dựa vào B để in ra thôi.
Bài 2: bạn biết hàm pos chưa? Cứ tìm X trong S, xóa đi, cứ như thế tới khi pos(x,s)=0 thì kiểm tra: nếu S= rỗng thì tức là S được tạo liên tục từ X, nếu không thì là không phải.
Bài 3: dùng hàm length để tìm độ dài. Dùng hàm pos để tìm số lần xuất hiện với vị trí của chúng.
Bài 4: dùng 1 biến đếm để đếm số lần xuất hiện của phần tử trong mảng.
Bài 5: Xóa đi tất cả các kí tự có trong S2 mà không có trong S1, sau đó so sánh từng kí tự (từ đầu tới cuối) của S2 với kí tự có vị trí tương ứng trong S1, nếu không giống nhau thì xóa đi kí tự trong S1, làm như thế tới khi hết S1 hoặc hết S2. Nếu kí tự cuối cùng của S2 giống kí tự cuối cùng của S1 (đã duyệt qua bước trước và tới được kí tự cuối cùng) thì tức là có thể từ S1 tạo ra S2, không là không thể.
Bài 6: Cách đơn giản là tạo 1 xâu đảo ngược với xâu ban đầu, so sánh với xâu ban đầu, nếu giống nhau thì là xâu đối xứng.
Bài 7 hơi phức tạp hơn chút:
Từ 1 duyệt tới hết xâu: tìm 1 vị trí mà đó có thể là tâm đối xứng của 1 xâu đối xứng (xâu đối xúng này chẵn thì tức là kí tự ở vị trí đó giống kí tự cạnh nó, xâu đối xứng có độ dài lẻ thì kí tự ở 2 vị trí cạnh nó giống nhau). Rồi từ vị trí đó lan rộng ra 2 bên, lấy vào xâu, tới khi xác định được xâu mà ta lấy ra đó không còn tính đối xứng thì lưu lại vị trí tâm, độ dài xâu, so sánh với xâu đối xứng có độ dài max. Làm như thế tới khi duyệt được hết xâu thì ta được kết quả.
Bạn đừng trách mình vì không viết code nha. Có lẽ mem của box pascal đều biết mình chỉ nêu ý tưởng chứ không viết code.
Mình tuân theo nguyên tắc: Chỉ nên cho người ta cái cần câu!
Chúc bạn học tốt và yêu thích môn Tin học._

----------


## pesttykl

b1.


```
const     fi='dulieu.inp';
            fo='dulieu.out';
var        a:array[1..10000] of longint;
            d:longint;
            f:text;
procedure inp;
begin
            assign(f,fi);
            reset(f);
           d:=0;
           while not(eof(f)) do
           begin
                     inc(d);
                     read(f,a[d]);
           end;
           close(f);
end;
procedure xuly;
var       max,min,i:longint;
           b:array[-10000..10000] of longint;
begin
           assign(f,fo);
           rewrite(f);
           max:=a[1];
           min:=a[1];
           for i:=2 to d do
           begin
                     if a[i]>max then max:=a[i];
                     if a[i]<min then min:=a[i];
           end;
           for i:=1 to d do inc(b[(a[i])]);
           for i:=min to max+1 do
           if b[i+1]<>0 then write(f,b[i+1],' ');
           close(f);
end;
begin
           inp;
           xuly;
end.
```

b2.


```
uses     crt;
var       m,i:byte;s:string;a:array[1..50] of byte;b:array[1..50] of string;
           kt:array[1..50] of boolean;
           s1:string;
begin 
           clrscr;
           readln(s);
           m:=0;
           for i:=1 to trunc(sqrt(length(s))) do
           if length(s) mod i=0 then
           begin
                      inc(m);
                      a[m]:=i;
           end;
           for i:=1 to m do b[i]:=copy(s,1,a[i]);

           fillchar(kt,sizeof(kt),false);
           i:=0;
           repeat
                      inc(i);
                      s1:=s;
                      while b[i]=copy(s1,1,length(b[i])) do delete(s1,1,length(b[i]));
                      if s1='' then kt[i]:=true;
           until i=m;
           i:=1;
           while (not kt[i]) and (i<=m) do inc(i);
           if i>m then writeln('0.')
           else write('X=',copy(s,1,length(b[i])));
           readln;
end.
```

----------


## ananhhoang

b3.


```
uses    crt;
var      s1,s2:string;
procedure     xuly;
var      u:string;
          i,d:longint;
          a:array[1..1000] of longint;
begin
          write('do dai s1:'); writeln(length(s1));
          write('do dai s2:'); writeln(length(s2));
          u:=s2;
          d:=0;
          while pos(s1,u)<>0 do
          begin
                    inc(d);
                    a[d]:=pos(s1,u);
                    delete(u,pos(s1,u),length(s1));
           end;
           write('so lan xuat hien :'); writeln(d);
           if d>0 then
           begin
                     write('tai cac vi tri:');
                     for i:=1 to d do
                     if i=1 then write(a[i],' ')
                          else write((a[i]+length(s1)),' ');
           end;
end;
begin
           clrscr;
           write('nhap s1:');readln(s1);
           write('nhap s2:');readln(s2);
           xuly;
readln;
end.
```

b4. đã có topic nói rồi anh chịu khó tìm lại nhé .

----------


## nguyendangvan

Bài 7 không cần vét cạn đâu, chỉ 1 lần chạy duyệt hết xâu là ok rồi, vì khi đã tìm được 1 xâu đối xứng trong xâu ban đầu, ta chỉ cần chạy tiếp từ vị trí cuối cùng của xâu đó tới cuối để tìm tiếp. Không cần vét cạn đâu bạn.

==================================================  ===========
Yêu cầu lần cuối: "Xem xét lời lẽ, nếu không sẽ bị cảnh cáo!"

----------


## noithatkienan

@tieulong : anh có thể nói rõ hơn về thuật toán chút ko ạ ?
Dạo này bận quá . Thầy cô bắt kt 1 tiết trước kỳ ngỉ tết nên ko có thời gian viết code . em thử nêu thuật toán mọi người cho ý kiến .
-Tất nhiên là phải duyệt từ đầu tới cuối xâu . 
-Khi tới kí tự s_ thì copy từ i+1 tới hết
-sau đó dùng hàm pos để tìm s trong xâu vừa cọp , rồi kiểm tra đối xứng như bt. 
-cuối cùng là xóa từ đầu xâu vừa cop tới ký tự s đầu tiên trong xâu đó .
Thuật toán còn cùi quá , mọi người đừng chê nha ._

----------


## khamnamkhoa

> @tieulong : anh có thể nói rõ hơn về thuật toán chút ko ạ ?
> Dạo này bận quá . Thầy cô bắt kt 1 tiết trước kỳ ngỉ tết nên ko có thời gian viết code . em thử nêu thuật toán mọi người cho ý kiến .
> -Tất nhiên là phải duyệt từ đầu tới cuối xâu . 
> -Khi tới kí tự s_ thì copy từ i+1 tới hết
> -sau đó dùng hàm pos để tìm s trong xâu vừa cọp , rồi kiểm tra đối xứng như bt. 
> -cuối cùng là xóa từ đầu xâu vừa cop tới ký tự s đầu tiên trong xâu đó .
> Thuật toán còn cùi quá , mọi người đừng chê nha ._


_
Thuật toán của bạn là cho bài 5 hay bài 7 vậy? Nếu là bài 7 thì mình chưa hiểu rõ thuật toán của bạn lắm vì khi chưa xóa S thì lấy pos vẫn là nó, có thay đổi gì đâu.
THuật toán của mình thì tư tưởng chủ đạo thế này:
Tìm tâm đối xứng của 1 xâu đối xứng có mặt trong xâu inp. nếu xâu đối xứng độ dài lẻ thì tức là các vị trí 2 bên của tâm đó phải bằng nhau. Nếu độ dài chẵn thì phía phải chỉ khác phía trái 1 vị trí. VD ABBA, ta lấy tâm là B. Khi tìm đến 1 tâm bất kì, thử lan rộng xâu đối xứng sang 2 bên tới khi lan ra mà không còn là đối xứng thì so sánh với xâu có độ dài lớn nhất ta đã tìm thấy.
Ta chỉ cần duyệt 1 lần thôi, thử tâm đối xứng từ 1 tới cuối xâu inp, tới khi duyệt xong là ta có được kết quả.
Có gì bạn không hiểu nữa thì post sớm nha, Tết mà, không có nhiều thời gian lắm đâu. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]( phải dọn nhà [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](_

----------


## Huongbavi

> Thuật toán của bạn là cho bài 5 hay bài 7 vậy? Nếu là bài 7 thì mình chưa hiểu rõ thuật toán của bạn lắm vì khi chưa xóa S_ thì lấy pos vẫn là nó, có thay đổi gì đâu.
> THuật toán của mình thì tư tưởng chủ đạo thế này:
> Tìm tâm đối xứng của 1 xâu đối xứng có mặt trong xâu inp. nếu xâu đối xứng độ dài lẻ thì tức là các vị trí 2 bên của tâm đó phải bằng nhau. Nếu độ dài chẵn thì phía phải chỉ khác phía trái 1 vị trí. VD ABBA, ta lấy tâm là B. Khi tìm đến 1 tâm bất kì, thử lan rộng xâu đối xứng sang 2 bên tới khi lan ra mà không còn là đối xứng thì so sánh với xâu có độ dài lớn nhất ta đã tìm thấy.
> Ta chỉ cần duyệt 1 lần thôi, thử tâm đối xứng từ 1 tới cuối xâu inp, tới khi duyệt xong là ta có được kết quả.
> Có gì bạn không hiểu nữa thì post sớm nha, Tết mà, không có nhiều thời gian lắm đâu. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]( phải dọn nhà [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA  l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR  EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](_


_

b7 ạ . em lấy hàm pos trong xâu copy ( em gọi là x cho dễ ) cơ . lại xóa trong x đến khi pos=0 thì tiếp tục tăng i . 
Nhưng nếu thuật toán của anh là tìm tâm đx thì em nghĩ vẫn phải lặp để kt độ đxứng có đúng ko ạ ?_

----------


## anhdjen

Thích thì vào download bài giải của tui về mà tham khảo là được ngay mà.

----------


## hungcong88

> Thích thì vào download bài giải của tui về mà tham khảo là được ngay mà.


nói như vậy làm sao đc hả anh ? download về mà cũng ko hiểu bản chất thuật giải thì có ý nghĩa gì đâu .

----------


## hvdnghia3

Sacklove với mình cùng chí hướng rồi, cái quan trọng là hiểu vs nắm rõ phương pháp, chứ không phải chỉ cần chương trình.
Để tìm tâm đối xứng thì đúng là ta cần lặp để duyệt, nhưng chỉ cần 1 lần lặp để tìm tâm và với 1 lần lặp, lan sang 2 bên nữa là ok vì 1 tâm không là tâm của 2 xâu đối xứng tách biệt nhau. Việc lan sang 2 bên cũng không mất quá nhiều thời gian đâu.
Thuật toán của sacklove liệu có ok với test này không?
ababac
Nếu như duyệt cách của bạn thì với hàm pos + thủ tục del, ta chỉ nhận được xâu đối xứng là aba hoặc bab. Trong khi đó xâu đối xứng dài nhất của test là ababa. 
Hàm pos dùng trong trường hợp xâu có nhiều kí tự giống nhau thì hiệu quả chắc ko cao lắm..

----------


## bedaukute22

> Sacklove với mình cùng chí hướng rồi, cái quan trọng là hiểu vs nắm rõ phương pháp, chứ không phải chỉ cần chương trình.
> Để tìm tâm đối xứng thì đúng là ta cần lặp để duyệt, nhưng chỉ cần 1 lần lặp để tìm tâm và với 1 lần lặp, lan sang 2 bên nữa là ok vì 1 tâm không là tâm của 2 xâu đối xứng tách biệt nhau. Việc lan sang 2 bên cũng không mất quá nhiều thời gian đâu.
> Thuật toán của sacklove liệu có ok với test này không?
> ababac
> Nếu như duyệt cách của bạn thì với hàm pos + thủ tục del, ta chỉ nhận được xâu đối xứng là aba hoặc bab. Trong khi đó xâu đối xứng dài nhất của test là ababa. 
> Hàm pos dùng trong trường hợp xâu có nhiều kí tự giống nhau thì hiệu quả chắc ko cao lắm..


đc chứ anh . trong xâu babac có 2 ký tự 'a' như vậy là em sẽ đc 2 lần với pos('a')
ý em là từ xâu 'babac' thì del 'ba' để còn lại 'bac' như vậy hàm pos sẽ tìm đc ký tự 'a' thứ 2.

----------


## thanhcanh

Xâu mình cho là ababac mà, có 3 a. Nhưng sao lại del ab đi? Del nó đi rồi thì khi mình xác định xâu đối xứng sẽ vất vả đấy.
Bạn có thể trình bày rõ hơn thuật toán được không?

----------


## VinhLink

> Xâu mình cho là ababac mà, có 3 a. Nhưng sao lại del ab đi? Del nó đi rồi thì khi mình xác định xâu đối xứng sẽ vất vả đấy.
> Bạn có thể trình bày rõ hơn thuật toán được không?


là như này :
+ khi xét tới xau[1] ='a' thì em sẽ copy('babac') sau đó dùng hàm pos kể kiểm tra
+ Khi đã có đc vị trí của ký tự đó ( trong trường hợp ví dụ này là ký tự 'a') thì sẽ biến đổi 1 chút các con số như: độ dài xâu , vị trí các ký tự để ktra .

----------


## TeamSEOAQ

Thế như vậy thì bạn định lấy pos tới khi không còn nữa hay là không còn tạo thành xâu đối xứng?

----------


## nhocmisu@gmail.com

> Thế như vậy thì bạn định lấy pos tới khi không còn nữa hay là không còn tạo thành xâu đối xứng?


khi nào pos cho giá trị =0 thì tiếp tục duyệt ký tự tiếp theo . Còn nếu gặp đc xâu đối xứng thì lưu lại vị trí và vẫn tiếp tục duyệt để tìm kiếm xâu đối xứng dài hơn .

----------


## danga

Thế thì ý tưởng cũng hợp lí đấy, ý của bạn là xuất phát từ 1 kí tự đầu tiên, đi tìm kí tự cuối cùng hả? Nhưng mà tốc độ của thuật toán này chắc không nhanh lắm nhỉ? Vì nó gần như duyệt toàn bộ các xâu nghi ngờ là đối xứng. Thuật toán của mình là chỉ tiếp tục với xâu mình biết là đối xứng. Bạn thử làm cả 2 thuật toán rồi so sánh tốc độ xem, mình cũng không chắc lắm.

----------


## quanglong87

> Thế thì ý tưởng cũng hợp lí đấy, ý của bạn là xuất phát từ 1 kí tự đầu tiên, đi tìm kí tự cuối cùng hả? Nhưng mà tốc độ của thuật toán này chắc không nhanh lắm nhỉ? Vì nó gần như duyệt toàn bộ các xâu nghi ngờ là đối xứng. Thuật toán của mình là chỉ tiếp tục với xâu mình biết là đối xứng. Bạn thử làm cả 2 thuật toán rồi so sánh tốc độ xem, mình cũng không chắc lắm.


em thì lại nghĩ khác . Làm sao để anh biết xâu nào ko đx rồi loại nó đi và chắn chắn xâu nào đối xứng để tiếp tục ? Vẫn phải kiểm tra . Có đúng ko ạ ???
Hơn nữa , chắc là anh phải dùng 1 vòng lặp để lan sang 2 bên và kiểm tra đối xứng vậy thì gần giống vét cạn rồi .
Em nghĩ như vậy có lẽ chưa chính xác lắm . anh cho em ý kiến với !!

----------


## thiendung

Tại 1 bước mình có thể biết chắc rằng mình lan sang 2 bên có còn là đối xứng không: mình chỉ cần kiểm tra 2 kí tự mình định lan sang nếu giống nhau thì tiếp tục vì xâu hiện tại đã đối xứng. Như thế công việc kiểm tra tính đối xứng thực chất chỉ là kiểm tra 2 kí tự có giống nhau không thôi. Sao bạn nào cũng nghĩ là vét cạn nhỉ? Bạn nên nhớ rằng thuật toán của mình là lan sang chỉ khi biết chắc nó sẽ đối xứng, còn thuật toán của bạn là miễn pos chưa bằng 0 thì lan sang rồi kiểm tra tính đối xứng. Như thế thì mình chắc chắn tốc độ của bạn sẽ không nhanh bằng của mình. Mình giải thích thế bạn hiểu chưa?

----------


## huongcao

> Tại 1 bước mình có thể biết chắc rằng mình lan sang 2 bên có còn là đối xứng không: mình chỉ cần kiểm tra 2 kí tự mình định lan sang nếu giống nhau thì tiếp tục vì xâu hiện tại đã đối xứng. Như thế công việc kiểm tra tính đối xứng thực chất chỉ là kiểm tra 2 kí tự có giống nhau không thôi. Sao bạn nào cũng nghĩ là vét cạn nhỉ? Bạn nên nhớ rằng thuật toán của mình là lan sang chỉ khi biết chắc nó sẽ đối xứng, còn thuật toán của bạn là miễn pos chưa bằng 0 thì lan sang rồi kiểm tra tính đối xứng. Như thế thì mình chắc chắn tốc độ của bạn sẽ không nhanh bằng của mình. Mình giải thích thế bạn hiểu chưa?


không hẳn là vét cạn nhưng lan sang thì không phải dụng vòng lặp while or repeat ạ ? còn thuật toán của em thì ko phải lan sang ạ . chỉ là tìm thấy vị trí thì kiểm tra nó thôi . em kiểm tra đối xứng bình thường chứ ko dùng vòng lặp .

----------


## linht1106k1

Bạn kiểm tra đối xứng kiểu gì? Đảo ngược xâu rồi so sánh với xâu cũ? Hay là 1 vòng for để kiểm tra? Tất cả các cách trên bản chất đều phải so sánh tối thiểu n/2 kí tự, chưa kể là bạn phải kiểm tra nhiều lần, tức là nhiều xâu lồng nhau, khi đó số lần kiểm tra của bạn sẽ rất nhiều. Cách của mình ấn định là kiểm tra từng kí tự của 2 phía, dùng while hay repeat đều như nhau cả. Bạn tự so sánh xem sao.

----------


## kowalsky

> Bạn kiểm tra đối xứng kiểu gì? Đảo ngược xâu rồi so sánh với xâu cũ? Hay là 1 vòng for để kiểm tra? Tất cả các cách trên bản chất đều phải so sánh tối thiểu n/2 kí tự, chưa kể là bạn phải kiểm tra nhiều lần, tức là nhiều xâu lồng nhau, khi đó số lần kiểm tra của bạn sẽ rất nhiều. Cách của mình ấn định là kiểm tra từng kí tự của 2 phía, dùng while hay repeat đều như nhau cả. Bạn tự so sánh xem sao.


với cách kiểm tra của anh thì cũng phải kiểm tra khoảng n/2 bước cho 1 xâu đối xứng ? vậy thì em nghĩ thuật toán của anh có thể nhanh hơn nhưng hơn không đáng kể .

----------


## HSCompany

Bạn chưa hiểu ý mình rồi, của bạn là phải liên tục kiểm tra các xâu có đối xứng không, như thế số bước kiểm tra 1 xâu có đối xứng không là n/2, nhưng lại mất nhiều lần kiểm tra tính đối xứng. Còn của mình chỉ 1 lần kiểm tra là ok.
VD nha: abcdbabcd
Thuật toán của bạn:
x1=a, tìm tới x6=a, kt đối xứng trong xâu 6 kí tự = 3 bước. {bước ở đây hiểu là biến chạy bao nhiêu}
x2=b, tìm tới x5=b, kt xâu 4 kí tự = 2 bước.
x3=c, tìm tới x8=c, kt xâu 6 kí tự = 3 bước.
x4=d, tìm tới x9=d, kt xâu 6 kí tự = 3 bước.
x5=b, tìm tới x7=b, kt xâu 3 kí tự = 2 bước. Được 1 xâu đx.
x6=a, pos =0.
x7, x8, x9 thôi không kt, Tổng số bước x6-> x9 =4 bước.
Tổng cộng: 19 bước.
Thuật toán của mình:
x1 -> x5, vì không thể là tâm nên chỉ mất 5 bước.
x6 là tâm, lan sang 2 bên mất 2 bước nữa là dừng (lan qua b thì dừng) mất thêm 2 bước.
x7->x9 không là tâm, mất thêm 3 bước.
Tổng cộng: 10 bước.
10 vs 19 -> gần nửa đúng không? 
Đây mới chỉ là 1 test nhỏ, 9 kí tự, với xâu 256 kí tự thì chắc là không tiết kiệm ít đâu bạn à. Nhưng dù sao đây cũng chỉ là 1 bài nhỏ, giới hạn 256, thế thì cách nào cũng chỉ hơn kém nhau tầm 1 vài % s thôi mà.

----------


## sevenup024

> Bạn chưa hiểu ý mình rồi, của bạn là phải liên tục kiểm tra các xâu có đối xứng không, như thế số bước kiểm tra 1 xâu có đối xứng không là n/2, nhưng lại mất nhiều lần kiểm tra tính đối xứng. Còn của mình chỉ 1 lần kiểm tra là ok.
> VD nha: abcdbabcd
> Thuật toán của bạn:
> x1=a, tìm tới x6=a, kt đối xứng trong xâu 6 kí tự = 3 bước. {bước ở đây hiểu là biến chạy bao nhiêu}
> x2=b, tìm tới x5=b, kt xâu 4 kí tự = 2 bước.
> x3=c, tìm tới x8=c, kt xâu 6 kí tự = 3 bước.
> x4=d, tìm tới x9=d, kt xâu 6 kí tự = 3 bước.
> x5=b, tìm tới x7=b, kt xâu 3 kí tự = 2 bước. Được 1 xâu đx.
> x6=a, pos =0.
> ...


ơ thế nhỡ xâu đx kiểu 'abccba' thì sao ạ ? lúc đó chẳng phải sẽ phải kiểm tra thêm 1 ký tự bên cạnh sao .

----------


## tradaquanmobi

Với xâu này thì chỉ có tại vị trí thứ 3 là mất thêm bước để kiểm tra thôi. Tất nhiên kt xâu lẻ sẽ không mất thêm bước, chỉ là kt xâu cc .. Khi đó bước kiểm tra cc là tâm rồi lan ra sẽ tương đương bước kt a ban đầu của bạn. Còn những kí tự khác do không thể là tâm nên sẽ kô kt . Với test này thì 2 thuật toán có tốc độ như nhau.
Thuật toán của mình sẽ kém hiệu quả khi bất kì 1 kí tự nào của xâu cũng là tâm của 1 xâu đx. VD aaaaaaaa
THuật toán của bạn cần tới các phép tính, tìm kiếm trên xâu, biến đổi xâu như: hàm pos là 1 lần duyệt tìm kiếm, thủ tục del cũng gần như thế, sau đó tiếp tục cộng xâu, cần 1 xâu khác để lưu. Nhưng ưu điểm là tốc độ của thuật toán không phụ thuộc vào test nhiều như của mình. Với thuật toán mình đưa ra, nếu không xác định được xâu đó dx chẵn hay lẻ sớm thì sẽ chậm, nhưng bù lại với việc chỉ cần kt 2 kí tự với nhau nên nói chung tốc độ của 2 thuật toán sẽ không hơn nhau là mấy trong những trường hợp test hiểm. 1 điều nữa là bài toán này do giới hạn nhỏ, nên với yêu cầu 1s 1 test thì cũng đơn giản thôi.

----------

