Trang 1/2 12 cuối
kết quả từ 1 tới 12 trên 14

Ai pro Pascal xem giúp em bài này đã đúng chưa

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 374302
    Giới tính: Nữ
    Bài gửi
    12

    Question Ai pro Pascal xem giúp em bài này đã đúng chưa

    Cô cho em bài làm qua tết như sau. Anh chị nào xem giúp em với.
    Tìm chuỗi:
    Cho một xâu S và một xâu T chỉ gồm các ký tự thường và hoa từ ‘a’ tới ‘z’ và các số từ ‘0’ tới ‘9’. Viết chương trình cho biết xâu T có phải là xâu con (liên tục) của S hay không. Nếu là xâu con thì cho biết vị trí đầu tiên bắt đầu xuất hiện xâu T trong S.

    Input: BAI1.INP
    Gồm 2 dòng:
    Dòng 1: xâu S có độ dài tối đa m, với 0 < m <= 10^6.
    Dòng 2: xâu T có độ dài tối đa n, với 0 < n <= 10^6.

    Output: BAI1.OUT
    Nếu xâu T không phải là xâu con của S thì ghi -1. Ngược lại thì ghi ra chỉ số của vị trí bắt đầu của xâu T ở trong S.

    Ví dụ:
    BAI1.INP BAI1.OUT
    tettetdenroi
    et
    2
    tetabcaabbcy
    bcaat
    -1

    Em đã làm rồi mà không biết có trường hợp nào ct sai không. Ngoài ra, ai chỉ giúp em làm sao làm cho nó nhanh hơn. Em thấy nó chạy khá chậm. Chiều dài chuỗi lớn hơn 10000 là phần nâng cao mà ct em chạy không nổi.
    Mã:
    var s,t : ansistring;
        i,j,vi_tri : longint;
        tim_duoc : boolean;
        fi,fo : text;
        
    begin
        assign(fi, 'BAI1.INP');
        reset(fi);
        readln(fi, s);
        readln(fi, t);
        close(fi);
        assign(fo, 'BAI1.OUT');
        rewrite(fo);
        tim_duoc:=false;
        i:=1;
        j:=1;
        vi_tri:=1;
        while (i <= length(s)) do
            begin
                if (s[i] = t[j]) then
                    begin
                        i:=i+1;
                        j:=j+1;
                    end
                else
                    begin
                        j:=1;
                        i:=i+1;
                        vi_tri:=i;
                    end;
                if (j > length(t)) then
                    begin
                        tim_duoc:=true;
                        writeln(fo, vi_tri);
                        break;
                    end;
            end;
        if (tim_duoc = false) then
            writeln(fo, -1);
        close(fo);
    end.
    Quick reply to this message Trả lời       

  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    đây là code dư sức chạy tới 10^6 nhé
    Mã:
    //code written by Phạm Thanh Nhân LHP
    const fi='string.inp';
          fo='string.out';
    
    
    var f:text;
        st,s,ss:ansistring; //max length=10^6
        n,i,j:longint; //do dai la 10^6
    
    
    begin
        assign(f,fi);
        reset(f);
          readln(f,s);
          readln(f,ss);
        close(f);
    
    
        assign(f,fo);
        rewrite(f);
          j:=0; // co hieu
          for i:=1 to length(s)-length(ss)+1 do
            begin
              if s[i]=ss[1] then
                begin
                  st:=s;
                  delete(st,i,length(ss));
                  insert(ss,st,i);
                  if st=s then
                    begin
                      writeln(f,i);
    
    
                      j:=1; // la da thuc hien
                      break;
                    end;
                end;
            end;
          if j=0 then writeln(f,-1);
        close(f);
    end.

  3. 2 thành viên đã cảm ơn phamthanhnhan:


  4. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 374302
    Giới tính: Nữ
    Bài gửi
    12

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Em cám ơn anh. Em thử trường hợp sau thì ct chạy quá chậm. Có cách nào cho nó chạy nhanh hơn không? Mà code của em có đúng không?
    Mã:
    ss:='1111111110';
    s:='';
    for i:=1 to 1000000 do
        s:=s+'1';

  5. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Trích Nguyên văn bởi nngoc Xem bài viết
    Em cám ơn anh. Em thử trường hợp sau thì ct chạy quá chậm. Có cách nào cho nó chạy nhanh hơn không? Mà code của em có đúng không?
    Mã:
    ss:='1111111110';
    s:='';
    for i:=1 to 1000000 do
        s:=s+'1';
    mình chưa hiểu lắm, vì thuật toán là O(n) với n<=10^6 và các thao tác string cơ bản thì ko có chậm, test nào chậm bạn up lên mình xem thử với

  6. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 374302
    Giới tính: Nữ
    Bài gửi
    12

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Em viết code tạo chuỗi s và ss bằng tay. Chuỗi s là 10^6 con số 1, chuỗi ss là '1111111110'. Em chạy hơn 1 phút chưa ra.

  7. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Trích Nguyên văn bởi nngoc Xem bài viết
    Em viết code tạo chuỗi s và ss bằng tay. Chuỗi s là 10^6 con số 1, chuỗi ss là '1111111110'. Em chạy hơn 1 phút chưa ra.
    do bạn dùng linear (tuyến tính), nếu mà bạn từng học qua binary search thì người ta tạo chuỗi không làm như vậy
    Mã:
    //code linear tạo chuỗi length=1024
    for i:=1 to 1024 do 
      s:=s+'1';
    Mã:
    //code theo tư tưởng làm việc của binary search
    s:='1';
    for i:=1 to 10 do 
      s:=s+s;
    đó là sự khác biệt của làm tuyến tính với theo tư tưởng của binary search

  8. Đã cảm ơn phamthanhnhan:

    nngoc 

  9. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 374302
    Giới tính: Nữ
    Bài gửi
    12

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Ý của em là: chuỗi s và ss được tạo như thế thì ct của anh chạy không ra kết quả. Em đã tạo được chuỗi s gồm 10^6 con số 1 rồi.

  10. #8
    Ðến Từ
    Đồng Nai
    Thành Viên Thứ: 374500
    Giới tính: Nam
    Bài gửi
    5

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Dùng hàm Pos(T,S) để kiểm tra vị trí xuất hiện của xâu T trong xâu S.
    Nếu không tìm thấy thì trả về giá trị 0.
    Code:
    Mã:
    If pos(t,s)=0 then writeln('-1') else writeln(pos(t,s));

  11. Đã cảm ơn Vuh:

    nngoc 

  12. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 374302
    Giới tính: Nữ
    Bài gửi
    12

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Trích Nguyên văn bởi Vuh Xem bài viết
    Dùng hàm Pos(T,S) để kiểm tra vị trí xuất hiện của xâu T trong xâu S.
    Nếu không tìm thấy thì trả về giá trị 0.
    Code:
    Mã:
    If pos(t,s)=0 then writeln('-1') else writeln(pos(t,s));
    Cô của em không cho dùng hàm có sẵn.

  13. #10
    Ðến Từ
    Đồng Nai
    Thành Viên Thứ: 374500
    Giới tính: Nam
    Bài gửi
    5

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Bạn thử code này nhé, chạy đến 20000 mà chưa tới 1s đâu.
    Mã:
    uses crt;
    var
            s,t:ansistring;
            i:qword;
    begin
            clrscr;
            {$ Tao xau S la 10000 ki tu }
            s:='';
            i:=0;
            while i<20000 do
                    begin
                            inc(i);
                            s:=s+'a';
                    end;
            writeln(length(s));
            t:='b';
            {write('Nhap s: ');
            readln(s);
            write('Nhap t: ');
            readln(t);}
            i:=1;
            while i<length(s) do
                    begin
                            if copy(s,i,length(t))=t then
                                    begin
                                            writeln(i);
                                            readln;
                                            exit;
                                    end;
                            inc(i,1);
                    end;
            writeln('-1');
            readln
    end.
    Ở đây mình tạo xâu S là 'aaa...' và tìm chữ 'b' trong xâu đó. Do vậy nên chương trình sẽ chạy hết cả xâu.

  14. Đã cảm ơn Vuh:

    nngoc 

  15. #11
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 374302
    Giới tính: Nữ
    Bài gửi
    12

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Trích Nguyên văn bởi Vuh Xem bài viết
    Bạn thử code này nhé, chạy đến 20000 mà chưa tới 1s đâu.
    Mã:
    uses crt;
    var
            s,t:ansistring;
            i:qword;
    begin
            clrscr;
            {$ Tao xau S la 10000 ki tu }
            s:='';
            i:=0;
            while i<20000 do
                    begin
                            inc(i);
                            s:=s+'a';
                    end;
            writeln(length(s));
            t:='b';
            {write('Nhap s: ');
            readln(s);
            write('Nhap t: ');
            readln(t);}
            i:=1;
            while i<length(s) do
                    begin
                            if copy(s,i,length(t))=t then
                                    begin
                                            writeln(i);
                                            readln;
                                            exit;
                                    end;
                            inc(i,1);
                    end;
            writeln('-1');
            readln
    end.
    Ở đây mình tạo xâu S là 'aaa...' và tìm chữ 'b' trong xâu đó. Do vậy nên chương trình sẽ chạy hết cả xâu.
    Em cám ơn anh. Khi S và đặc biệt là T dài ra thì hình như chạy không nổi. Em thử trường hợp chuỗi S lên 10^5 và T là 20000 thì thấy chậm hẳn.

  16. #12
    Ðến Từ
    Đồng Nai
    Thành Viên Thứ: 374500
    Giới tính: Nam
    Bài gửi
    5

    Reply: Ai pro Pascal xem giúp em bài này đã đúng chưa

    Code của anh vẫn chạy bình thường mà, đã tăng S lên 10^5 và T lên 20 000 vẫn chỉ xấp xỉ 1s thôi.
    Mã:
    uses crt;
    var
            s,t:ansistring;
            i:qword;
    begin
            clrscr;
            s:='';
            i:=0;
            while i<100000 {10^5} do
                    begin
                            inc(i);
                            s:=s+'a';
                    end;
            i:=0;
            while i<20000 do
                    begin
                            inc(i);
                            t:=t+'b';
                    end;
            {write('Nhap s: ');
            readln(s);
            write('Nhap t: ');
            readln(t);}
            i:=1;
            while i<length(s) do
                    begin
                            if copy(s,i,length(t))=t then
                                    begin
                                            writeln(i);
                                            readln;
                                            exit;
                                    end;
                            inc(i,1);
                    end;
            writeln('-1');
            readln
    end.
    Mà hình như là đọc từ file với dữ liệu quá lớn sẽ rất lâu, file chứa cả S và T tổng cộng là 100 000+20 000=120 000 byte=120 MB.
    Bạn thử bỏ phần đọc file xem tốc độ có được cải thiện không.

Trang 1/2 12 cuối