字符串匹配：朴素模式匹配算法

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

算法思想

1. 将主串与模式串长度相同的子串搞出来，挨个与模式串对比
2. 当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串。

代码实现：

#include<iostream>
using namespace std;
#include<string>

//从pos位置开始，返回子串在主串中的位置
int  brute_force(string S, string T, int pos)
{
	int i = pos;
	int j = 0;
	int Slen = S.length();
	int Tlen = T.length();

	if (pos<0 && pos>Slen) //处理不正常输入
	{
		return -1;
	}
	while (i < Slen && j < Tlen)
	{
		if (S[i] == T[j])
		{
			++i;
			++j;
		}
		else //指针后退重新开始匹配
		{
			i = i - j + 1; 
			j = 0;
		}
	}
	if (j >= Tlen)
	{
		return i - Tlen; //返回第一次相等的位置
	}
	else
	{
		return -1;
	}
}
int main()
{
	string S = "abababcdef";
	string T = "def";
	int ret = brute_force(S, T, 1);
	cout << ret << endl;
	return 0;
}
           

算法复杂度分析：

若模式串长度为m，主串长度为n 。则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较

最坏时间复杂度：O(nm)；

最好时间复杂度: O(1)；