大圣苦苦寻找紫霞仙子，，，，，

（*）暴力匹配算法

问题：有两个字符串，s1是母串，s2是子串，要在母串中找子串出现的位置。

s1： SJHETCSAGYA
s2： CS

用暴力匹配思路就是：用s1[i]和s2[j]去匹配，如果匹配成功，i++，j++，即s1和s2都后移一位，匹配下一位；如果匹配失败，让i=i-j+1；j=0；即让s1后移一位，s2回溯，从s1的下一位重新匹配；
代码如下：

#include<iostream>
#include<string.h>
using namespace std;
int violence(char *s1, char *s2)     //暴力匹配算法
{
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	int i, j;
	for (i = 0, j = 0; i < len1&&j < len2;)
	{
		if (s1[i] == s2[j])        //如果匹配成功，i++，j++；即s1和s2都后移，匹配下一位；
		{
			i++;
			j++;
		}
		else                       //如果匹配失败，让s1后移，s2回溯；重新进行匹配下一位；
		{
			i = i - j + 1;
			j = 0;
		}
	}
	if (j == len2)                //找到s2，就返回它的位置；
		return i - j;
	else
		return -1;
}
int main()
{
	char s1[1005], s2[1005];
	cin >> s1 >> s2;
	int k=violence(s1, s2);
	cout << k << endl;
	return 0;
}

图解：

第一次循环
s1[0]=S，s2[0]=C，即匹配失败，执行“i = i - j + 1; j = 0;”，执行后i=1，j=0；相当于s2后移一位与s[1]进行匹配；

第二次循环
s1[1]=J，s2[0]=C，又匹配失败，执行“i = i - j + 1; j = 0;”，执行后i=2，j=0；相当于s2后移一位与s[1]进行匹配；

第三次循环
s1[2]=H，s2[0]=C，又匹配失败，执行“i = i - j + 1; j = 0;”，执行后i=3，j=0；相当于s2后移一位与s[1]进行匹配；

第四次循环
s1[3]=E，s2[0]=C，又匹配失败，执行“i = i - j + 1; j = 0;”，执行后i=4，j=0；相当于s2后移一位与s[1]进行匹配

第五次循环
s1[4]=T，s2[0]=C，又匹配失败，执行“i = i - j + 1; j = 0;”，执行后i=5，j=0；相当于s2后移一位与s[1]进行匹配

第六次循环
s1[5]=C，s2[0]=C，匹配成功，执行“ i++；j++；”，执行后i=6，j=1；

第七次循环
s1[6]=S，s2[1]=S，匹配成功，执行“ i++；j++；”，执行后i=7，j=2；此时j不满足循环条件”j<len2"；所以不再执行循环。返回子串的位置：k=i-j=7-2=5;

大圣一路披荆斩棘，终是找到了紫霞仙子，虽然时间长了一点，但比起一万年来，还是短的；

暴力匹配算法得时间复杂度太高，很容易超时，为了让大圣早点找到紫霞仙子，所以，才有了KMP算法。
下一篇，KMP算法。