字符串模式匹配
在主串中找到模式串相同的子串，并返回其所在的位置。
子串和模式串的区别
子串：主串的一部分，一定存在
模式串：不一定能在主串中找到
字符串模式匹配
朴素模式匹配算法
主串长度为n，模式串长度为m
朴素模式匹配算法：将主串中所有长度为m的子串(最多对比n-m+1个子串)依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止
index定位操作就是使用朴素模式匹配算法实现的
使用数组下标匹配
// 函数Index：在主串S中查找子串T的位置
// 返回值：如果找到子串，返回子串在主串中的位置（从1开始计数）
// 如果没有找到，返回0
int Index(SString S, SString T) {int i = 1, j = 1;while (i <= S.length && j <= T.length) {if (S.ch[i] == T.ch[j]) {++i; ++j; // 如果当前字符匹配，继续比较下一个字符} else {i = i - j + 2; // i回退到下一个可能的子串的起始位置j = 1; // j重置为1，重新开始匹配}}if (j > T.length)return i - T.length; // 如果找到子串，返回子串在主串中的位置elsereturn 0; // 如果没有找到子串，返回0
}
设主串长度为n，模式串长度为m，则最坏时间复杂度=O(nm)
最坏的情况，每个子串都要对比m个字符，共n-m+1个子串，复杂度=O((n-m+1)m)=O(nm)
注：很多时候，n>>m
总结
