题目描述
给定一个文本串text和模式串pattern，从文本串中找出模式串第一次出现的位置
先来看最简单的方法，方便理解题目，也就是暴力求解
暴力求解
放大上面的图，得到下面这个。题目要求匹配到整个字符串，从开始匹配考虑。
用模式串的首元素去匹配文本串的每一个元素，如果能匹配到，则依次向后匹配，直到所有的模式串匹配成功。
如果模式串中有一个不匹配，则pattern回到首元素匹配test中的下一元素。
这里需要注意的是，模式串首元素需要匹配的最后一个元素是text-j，因为如果匹配到最后，模式串比text长是没有意义的。
整个流程，可以想象是先把模式串与text对齐，然后相对于text依次后移一位，拖动pattern，每次移动都比较整个pattern模式串每个元素（理解这个有助于后面分析）
关键代码如下
int search(const char*s, const char*p)
{
int i = 0;//用于标记匹配到text字符串的位置
int j = 0;//标记模式串中匹配的位置
int size = (int)strlen(p);
int nLast = (int)strlen(s) - size; //此处为匹配到text中最长位置
while((i <= nLast) && (j < size))
{
if (s[i+j] == p[j])
{
j ++;
}
else{
i++;
j = 0; //j回到模式串首元素
}
}
if(j >= size)
return i;
return -1;
}
记text长度为N，pattern长度为M。在这个方法中，时间复杂程度为O(M*N)，空间复杂程度为O(1)
进一步分析：
在暴力求解中，为什么模式串的索引 j 会回溯？原因是模式串需要依次匹配整个才能知道是否完全匹配。
所以，增加一个条件，如果模式串的字符两两不相等。也就意味着模式串只要一次不匹配，整个 j 的长度都不会匹配上，就可以向后拖动pattern到自身长度的位置。
即，如果发生了不匹配，则向后移动 i+j 个位置开始匹配。
现在整个算法的时间复杂度退化成了O(N)，但这是在模式串两两不等的情况下才有的结论。那这个条件可以弱化吗？
当然是可以，弱化后条件变为：模式串首字符和其他字符不相等。