โปรแกรม C++ เพื่อใช้การจับคู่สตริงโดยใช้ Vectors

นี่เป็นวิธีการจับคู่สตริงอีกวิธีหนึ่ง ในแนวทางนี้ เรากำลังค้นหาสตริงย่อยโดยใช้เวกเตอร์

ใน C ++ เราสามารถสร้างเวกเตอร์ได้อย่างง่ายดายโดยใช้ไลบรารีมาตรฐาน เรากำลังนำสตริงหลักและสตริงที่จะค้นหาเป็นเวกเตอร์ จากนั้นค้นหาลงในสตริงหลัก เมื่อพบหนึ่งรายการที่ตรงกัน ฟังก์ชันจะส่งกลับที่อยู่และลบออกจากสตริงหลัก ดังนั้นในการทำซ้ำครั้งถัดไป มันเริ่มจากตำแหน่ง 0 แล้วค้นหาอีกครั้ง

เราใช้การวนซ้ำและค้นหาการจับคู่ซ้ำหลายครั้งเพื่อส่งคืนตำแหน่งสำหรับเหตุการณ์ที่เกิดขึ้นหลายครั้ง

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

อัลกอริทึม

vector_pattern_search(main, substr)

ป้อนข้อมูล − ข้อความหลักและสตริงย่อย

ผลผลิต − ตำแหน่งที่พบรูปแบบ

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