子字符串查找(暴力查找之显式回退) -- C++实现


测试代码

//main.cpp
#include "Component.h"

// 显式回退
int ViolentSearch(string pat,string txt,int iBegin = 0)
{
	int M = pat.length();
	int N = txt.length();

	// i用于跟踪文本
	// j用于跟踪模式
	int i = iBegin;
	int j = 0;
	for (; i < N && j < M; i++)
	{
		// i相当于ViolentSearch的 i + j
		// 此处的i指向的是已匹配过的字符系列的末端
		if (txt.at(i) == pat.at(j))
			j++;
		else
		{
			i -= j; // 回退
			j = 0;
		}
	}

	if (j == M)
	{
		return i - M;
	}

	return -1;
}

int main(int argc, char* argv[])
{
	string txt  ="qwhafhsjhfq87230878yqsdhfq9278r5278042yr5123qw8r098qthghasdfjhghajf08791232q9483r09q3uif123";
	int index1 = ViolentSearch("123",txt);
	cout << index1 << endl;
	cout << ViolentSearch("123",txt,index1+3) << endl;
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。