C++ Program to Implement String Matching Using Vectors

นี่คือ string matching method อีกวิธีหนึ่ง ในแนวทางนี้ เราค้นหา substring โดยใช้ vectors

ใน C++ เราสามารถสร้าง vectors ได้ง่ายด้วย standard library เราเอา main string และ string ที่จะค้นหาเป็น vector แล้วค้นหาใน main string เมื่อเจอ match หนึ่งครั้ง ฟังก์ชันจะคืนค่าที่อยู่ และลบออกจาก main string ดังนั้นใน iteration ถัดไป จะเริ่มจากตำแหน่ง 0 และค้นหาใหม่

สำหรับ multiple occurrences เราใช้ loops และค้นหา match ซ้ำๆ และคืนค่าตำแหน่ง

Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern "ABC"
Output: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Algorithm

vector_pattern_search(main, substr)

Input - The main text and the substring.

Output - location where patterns are found

Begin
    p := starting point of the main string
    while r is not at the end of substr and p is not at the end of main, do
        r := starting of substr
        while item at position p & r are not same, and p in main, do
            p := p + 1
            i := i + 1
        done
        q := p
        while item at pos p & r are same, and r in substr and p in main, do
            p := p + 1
            i := i + 1
            r := r + 1
        done
        if r exceeds the substr, then
            delete first occurrence of substr from main
            return the position where substr is found
        if p exceeds main string, then
            return 0
            q := q + 1
            p := q
    done
End

ตัวอย่างโค้ด

#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;
    }
}

ผลลัพธ์

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