Một đoạn đầu cho BTL ..Tìm kiếm xâu mẫu

LỜI NÓI ĐẦU
Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày. Trong tin học nó đặt nền móng cho nhiều tác vụ tính toán quan trọng. Bài toán tìm kiếm là sự xác định vị trí của một hay nhiều phần tử, gọi là đối trị tìm kiếm (Argument), trong một bảng liệt kê (có thứ tự hoặc không có thứ tự) các phần tử. Mỗi phần tử được đại diện bằng một khoá (Key) phục vụ cho tìm kiếm.
Những ứng dụng của tìm kiếm thì rất đa dạng, cũng như có rất nhiều các thuật toán với đặc trưng và hiệu năng khác nhau. Bình thường với một danh sách chưa sắp xếp, bạn tìm kiếm bằng cách duyệt tuần tự. Đây là cách đơn giản, những rất chậm và ít được sử dụng, đặc biệt khi dữ liệu lớn.Phương pháp Tìm kiếm xâu mẫu (String Searching) được sử dụng rộng rãi ,Ở thuật toán này gồm có : Thuật toán trực tiếp (Naïve algorithm) , Thuật toán Boyer-Moore , Thuật toán Rabin-Karp và Thuật toán Knuth-Mooris-Pratt (MP).
Sau đây chúng ta đi sâu vào tìm hiếu các thuật toán này :

Tìm kiếm xâu mẫu : (string searching)
Phát biểu bài toán.
Xâu(strings) là dãy kí hiệu lấy từ bảng kí hiệu(alphabet) Σ. Kí hiệu T[i..j] là xâu con của xâu T bắt đầu từ vị trí i và kết thúc ở vị trí j.
Trượt(Shifts) . Giả sử T1 và T2 là 2 xâu : |T1|=m ; |T2|=n . T1 xuất hiện nhờ trượt đến s trong T2 nếu
T1[1 .. m] = T2[s+1 .. s+m]
Giả sử T1 và T2 là 2 xâu. Nếu T1 xuất hiện nhờ trượt đến s trong T2 thì s được gọi là vị trí khớp của T1 trong T2 và ngược lại s được gọi là vị trí không hợp lệ
Bài toán tìm kiếm xâu mẫu (The string Matching Problem)
Cho xâu T độ dài n(T được gọi là văn bản) và xâu P độ dài m(P được gọi là xâu mẫu) . Tìm tất cả các vị trí khớp của P trong T
Các ứng dụng của bài toán :
Trong thu thập thông tin (information retrieval)
Trong soạn thảo văn bản (text editing)
Trong tính toán sinh học (Computational biology)
…..


I : Thuật toán trực tiếp (Naïve algorithm)

Ý tưởng : Dịch từng vị trí s=0,1,...n-m, với mỗi vị trí xem xâu mẫu có xuất hiện ở vị trí đó không
Code :
#include<stdio.h>
#include<conio.h>
{
void NaiveSM(char* P,int m,char* T,int n){
int i,j;
for(j=0;j<=n-m;j++){
for (i=0;i<m&&P[i]==T[i+j];i++)
if (i>=m) OUTPUT(j);
}
}
….

Có phải Bạn này học ở giảng đương D3-101 không?

Đúng rồi bạn

Thẻo nào nhìn mặt quen quá . Admin làm song báo cáo nhập môn chưa? hôm nay nộp đúng không Admin ?

Hôm nay nộp đâu .. hình như là tuần sau .. nhóm bọn t làm xong rồi .. đi in nữa là xong .. nhóm bạn thế nào rồi

Nhóm mình cũng làm song rồi. In rồi còn làm slide để thuyết trình nữa là song .
CÒn cái báo cáo CTDL đang tìm tài liệu làm thì tìm thấy 4rum của bạn. Rất bổ ích Thanks nhé

bạn làm BTL đề tài mấy ??? forum mới lập nên cũng chưa có gì :d ban thông cảm

Mình làm đề tài 9 giống bạn nè. Nhưng mà lười học môn này quá nên chưa biết làm như thế nào nên đang phải đi tìm tài liệu về để làm. ( .
Nhất định mình sẽ cung bạn đóng ghóp cho 4rum mạnh moà .Có gì hôm nào đi uống nước

Vậy cảm ơn bạn nhiều Nhất định rồi .. Đề 9 có 4 phần 4 người mỗi ng làm 1 phần .. t làm phàn đầu nên Post đc 1 tí thê thôi .. hôm nào cả nhóm hợp lại bài hoàn chỉnh t sẽ post đầy đủ lên đây cho mọi ng tham khảo

Ủa sao t không thấy bàn bạc gì về vụ nhóm nhỉ. T cũng đề tài 9 .
Mà 1 nhóm có 3 bạn trở xuống thôi mà Quang . T cũng làm đc kha khá roài nhưng mà chắc chỉ + ~ 1 điểm

Nhóm t thấy có 4 đứa - cũng chả hiểu .. hôm nọ chia nhau ra làm rồi nhóm phân theo lớp những đứa gần tên nhau thì phải

Ohm, Quang chek lại các bạn xem. HÌnh như 1 nhóm chỉ 3 người thì phải.