Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    daotrang

    daotrang
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Trong phần giới thiệu về thuật toán so khớp chuỗi KMP trên lớp (phần slide thầy đã gửi) có trình bày thuật toán xây dựng bảng next(k) thứ 2. Phần giả mã:
    Tính next(k), k= 1, 2, ...,m
    FOR(k=2;k<=m;k++)
    r = k-1;
    j = 1;
    WHILE (j>0)
    {
    WHILE((r>0)&&(P[r]==P[k]))r--;
    j=r-1;i=k-1;
    WHILE ((j>0)&&(P[j]==P[i])){j--;i--;}
    if (j>0) r--;
    }
    next[k]=r;
    Em đọc mãi mà chưa tìm ra ý tưởng cải tiến bảng next(k)ở đây. Bác nào biết xin vui lòng chỉ giáo hay có ý tưởng gì đưa lên góp ý cho em với. Thank you so much :)

    Cuong01111

    avatar
    Thành viên cao cấp
    Thành viên cao cấp
    Chào em,
    anh cũng đã code phần tính hàm next này và chạy cả bằng tay nữa. Tuy nhiên, cả 2 cách trên đều không đưa ra được kết quả như Ví dụ mà thầy đã cung cấp trong slide. Em phải suy nghĩ cách code khác.

    daotrang

    daotrang
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Em chưa muốn bàn luận đến code vì chuyển từ giả mã sang C đôi khi cũng có thể sai do sự khác biệt ngôn ngữ quy định. Phần next(k) thứ nhất nếu chuyển y nguyên giả mã sang code cũng đã sai dù thuật toán không có gì sai. Em chỉ muốn hỏi ý tưởng của phần cải tiến này, cách tiếp cận nó hợp lý và tốt hơn next(k) trước thôi. Thầy lại mặc định đây là phần rõ ràng, không có gì đáng bàn cả mà em không tiếp cận tốt vấn đề nên hơi lăn tăn chút. Mong các tiền bối tiếp tục chỉ giáo!

    HaiYen

    HaiYen
    Thành viên cao cấp
    Thành viên cao cấp
    Theo em thì ý tưởng của bài toán này không có gì là khó hiểu. Mục đích hình như là để nhảy một đoạn càng xa càng tốt. Việc nhảy này thường được áp dụng cho các bài toán so khớp chuỗi. Lẽ ra người ta phải tìm lần lượt từng phần tử trong 2 chuỗi thì người ta sẽ tìm theo một kiểu nào đấy để tránh trường hợp phải lần từng tí một đỡ mất công. Ở đây em cảm giác là chuỗi có tên là P sẽ dài hơn nhiều lần so với chuỗi con cần so sánh nên thuật toán ở đây chính là việc nhảy các chỉ số, để đưa thứ tự so khớp chỗi lẽ ra đến điểm x nào đó thì nó đã nhảy đi 1 đoạn k, đến vị trí x + k.

    dlvt2003

    dlvt2003
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Chắc Trang biết trong phần trình bày của thầy có 2 kiểu Next: Đầu tiên là của thuật MP và sau là của KMP!! Cái này hầu hết các trang trên mạng nhầm đấy trong đó có cả bác Wikipedia!
    Của thầy chuẩn đấy, lúc trước học anh thấy nó đúng mà!!em xem lại đi nha!! Chúc e thành công!!

    daotrang

    daotrang
    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Thanks các tiền bối đã chỉ giáo. Em đã xem xét lại vấn đề và thấy nội dung thầy trình bày là hoàn toàn chính xác, không có gì nhầm lẫn cả. Chạy bằng tay là ổn, chuyển sang Pascal không khó khăn gì vì chỉ số của phần giả mã của thầy và Pascal là khớp, chuyển sang C thì có đôi chút khác biệt về chỉ số chứ bản chất thuật toán và ý tưởng vẫn như thế. Đúng là cách tiếp cận vấn đề khó khăn một chút vì em tham khảo một số tài liệu trên mạng, nó khác phần giới thiệu của thầy nhưng không hẳn là sai. Phù, giờ mới thấy là cái bài em nộp chán quá, không biết mai lên trình bày có gỡ gạc được không. :(

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of https://khmt.123.st

    Create a forum on Forumotion | Khoa học | Giáo dục, giảng dạy | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất