使用向量实现字符串匹配的 C++ 程序

c++server side programmingprogramming

这是另一种字符串匹配方法。在这种方法中,我们使用向量搜索子字符串。

在 C++ 中,我们可以使用标准库轻松创建向量。我们将主字符串和要搜索的字符串作为向量,然后将其搜索到主字符串中。当找到一个匹配项时,函数将返回地址,并将其从主字符串中删除。因此在下一次迭代中,它从位置 0 开始并再次搜索。

对于多次出现的情况,我们使用循环并反复搜索匹配项,并返回位置。

输入:主字符串:"ABAAABCDBBABCDDEBCABC",模式"ABC"
输出:在位置 4 处找到模式
在位置 10 处找到模式
在位置 18 处找到模式

算法

vector_pattern_search(main, substr)

输入 − 主文本和子字符串。

输出 − 找到模式的位置

开始
   p := 主字符串的起始点
   当 r 不在 substr 的末尾且 p 不在 main 的末尾时,执行
      r := substr 的起始点
      当 item 在位置 p & r 不相同,并且 main 中的 p 执行
         p := p + 1
         i := i + 1
      done
      q := p
      while item at pos p & r 相同,并且 substr 中的 r 和 main 中的 p 执行
         p := p + 1
         i := i + 1
           r := r + 1
      完成
      如果 r 超出 substr,则
         从主字符串中删除第一个出现的 substr
         返回找到 substr 的位置

      如果 p 超出主字符串,则
         返回 0
         q := q + 1
           p := q
   完成
结束

示例代码

#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

相关文章