Đây là phương pháp khớp chuỗi khác. Trong cách tiếp cận này, ta tìm chuỗi con dùng vector.
Trong C++, có thể tạo vector dễ dàng dùng thư viện chuẩn. Ta lấy chuỗi chính và chuỗi cần tìm làm vector, sau đó tìm trong chuỗi chính. Khi tìm thấy một khớp, hàm trả về địa chỉ và xóa nó khỏi chuỗi chính. Vì vậy, lần lặp tiếp theo bắt đầu từ vị trí 0 và tìm lại.
Đối với nhiều lần xuất hiện, dùng lặp và tìm khớp liên tục, trả về vị trí.
Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern "ABC" Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
Thuật toán
vector_pattern_search(main, substr)
Input - Văn bản chính và chuỗi con.
Output - vị trí tìm thấy mẫu.
Begin
p := điểm bắt đầu chuỗi chính
while r không ở cuối substr và p không ở cuối main, do
r := bắt đầu substr
while item tại vị trí p & r không cùng, và p trong main, do
p := p + 1
i := i + 1
done
q := p
while item tại pos p & r cùng, và r trong substr và p trong main, do
p := p + 1
i := i + 1
r := r + 1
done
if r vượt quá substr, then
xóa lần xuất hiện đầu của substr từ main
trả về vị trí tìm thấy substr
if p vượt quá main string, then
return 0
q := q + 1
p := q
done
End
Ví dụ mã
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void take_string(vector<char> &string){
char c;
while(true){
c = getchar();
if(c == '\n'){
break;
}
string.push_back(c);
}
}
void display(vector<char> string){
for(int i = 0; i<string.size(); i++){
cout << string[i];
}
}
int match_string(vector<char>& main, vector<char> substr){
vector<char>::iterator p,q, r;
int i = 0;
p = main.begin();
while (r <= substr.end() && p <= main.end()){
r = substr.begin();
while (*p != *r && p < main.end()){
p++;
i++;
}
q = p;
while (*p == *r && r <= substr.end() && p<=main.end()){
p++;
i++;
r++;
}
if (r >= substr.end()){
main.erase(main.begin(), q + 1);
return (i - substr.size() + 1);
}
if (p >= main.end())
return 0;
p = ++q;
}
}
Kết quả
Enter main String: C++ is programming language. It is object oriented language Enter substring to find: language Match found at Position = 20 Match found at Position = 52