【数据结构】模式匹配算法 |
您所在的位置：网站首页 › 字符串处理算法是什么意思 › 【数据结构】模式匹配算法 |
【数据结构】模式匹配算法
|
一、模式匹配的概念 模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出该字串相同的所有子串，这就是模式匹配。其中原字符串成为目标串，给定的子串为模式串。通俗理解如下图1-1：
二、常用的模式匹配算法 1、朴素的模式匹配算法（也称简单匹配算法，Brute-Force简称BF算法） A.算法思想： 核心是穷举法。从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。 B.算法演示（给定目标串goodgoogle,模式串google）
C.代码实现 #include #include using namespace std; int Match1(string str, string searchStr) { int i = 0; int j = 0; while (i < str.size() && j < searchStr.size()) { if (str[i] == searchStr[j]) { i++; j++; } else//指针回退，重新开始匹配 { i = i - j + 1;//目标串回到匹配位置的下一位置 j = 0;//模式串回到起始0位置 } } if (j >= searchStr.size()) { return i - searchStr.size();//返回第一次匹配的首地址 } else { return -1; } } int main(){ string s = "goodgoogle"; string t = "google"; cout |
【本文地址】
今日新闻 |
推荐新闻 |