使用向量实现字符串匹配的 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