Thuật toán tìm kiếm(searching)

[dangnhapvn]

Mọi nguời gợi ý cho em bài tập này nhé.
Nếu ko dùng thuật toán tìm kiếm tuần tự thì còn thuật toán nào làm bài này nữa không nhỉ.

Input:  file ‘words.in’ chứa N từ (N<=10^5), mỗi từ là một xâu kí tự và viết trên 1 dòng. File 
‘lookingwords.in’ chứa M từ (M <= 10^7), mỗi từ là một xâu kí tự và viết trên 1 dòng.  
Problem: Với mỗi từ trong file ‘lookingwords.in’, tìm vị trí xuất hiện  trong file ‘words.in’. Với 
mỗi từ chỉ cần chỉ ra một vị trí. Nếu từ ñó không xuất hiện, thì vị trí ñược trả lại là ‘-1’. 
Output: ‘checkedwords.out’ chứa kết quả tìm kiếm. Dòng thứ i ghi vị trí xuất hiện của từ thứ i 
trong danh sách.  Vị trí các từ trong file được tính bắt đầu từ 1.  
 
Ví dụ 
words.in  lookingwords.in    checkedwords.out 
hello           love                  3 
world          you                  4 
love           K51CC              -1 
you            hello                 1 
K51CD

Mọi người gợi ý em nha.

[meoconlongvang]

Bài này bạn nên dùng bảng băm hoặc cây nhiều nhánh để cải thiện tốc độ tìm kiếm.

[zkday2686]

Cái này do số lượng số từ nhỏ nên chỉ cần đọc thông tin 2 file lên và thực hiện các thuật toán tìm kiếm chuổi là được mà.

[AlexF]

http://forums.congdongcviet.com/showthread.php?t=8746
1 bài toán tương tự như của cậu,nếu muốn phát triển lên bài của cậu thì làm thêm hàm return lại vị trí của từ là được

[dangnhapvn]

Cảm ơn các anh nhiều ạ, nhưng nhà em chưa được thầy dạy mảng băm và cây mới chết chứ, vài tuần nữa mới học Cây và mảng Băm. Giờ ko biết làm kiểu gì đây , chắc là phải tìm kiếm tuần tự thôi(gà quá).

[rox_rook]

Sort lại rùi binary search là xong chứ gì đâu hả cậu

#include <iostream>#include <algorithm>#include <vector>#include <string> int bS( const std::vector< std::string >& v, int beg, int end, const std::string& key ){    int pos;    if( beg > end ) {        pos = -1;    }    else {        int at = ( beg + end ) / 2;        if( key == v[ at ] )            pos = at;        else if( key < v[ at ] )            pos = bS( v, beg, end - 1, key );        else            pos = bS( v, beg + 1, end, key );    }    return pos;} int main(){    std::vector< std::string > vc;     vc.push_back( "I" );    vc.push_back( "love" );    vc.push_back( "C++" );     std::sort( vc.begin(), vc.end() );     std::cout << " \"love\" is at " << bS( vc, 0, vc.size(), "love" );     return 0;}

[dangnhapvn]

Sort-> ít nhất là O(n)log(n)-> hu hu + Tìm kiếm nhị phân = ????;
Tìm kiếm tuần tự-> O(n) + O(n)+.....+O(n) < O(n)log(n);
Hông biết có đúng ko nữa
Vấn đề ở đây là tối ưu.
Cảm ơn bạn.

[rox_rook]

Cái đó trường hợp trung bình, tìm kiếm nhị phân O( logn ), cậu cần tìm kiếm bao nhiêu cái ?
Giả sử cần tìm N phần tử :
Linear search gives : n x O( n ) = n^2
Binary search gives : O( n )log( n ) + n.log( n ) = log( n )( n + O( n ) ) = log( n ) x 2( n ) = log( n ) x n
which ones is faster ?

[dangnhapvn]

Đúng là "Binary search gives" nhanh hơn "Linear search gives" nhưng vấn đề ở đây là mảng chưa được sắp xếp-> làm thế nào mà dùng được
"Binary search gives". Nếu sắp xếp lại rồi dùng "Binary search gives"-> Chưa tối ưu->hổng biết có đúng ko

[AlexF]

Đúng là "Binary search gives" nhanh hơn "Linear search gives" nhưng vấn đề ở đây là mảng chưa được sắp xếp-> làm thế nào mà dùng được
"Binary search gives". Nếu sắp xếp lại rồi dùng "Binary search gives"-> Chưa tối ưu->hổng biết có đúng ko

dúng đấy,tìm kiếm nhị phân chỉ có thể dùng được khi dữ liệu được sắp xếp thôi,muốn tìm kiếm không sắp xếp chắc chỉ có cách for n thôi