串的模式匹配

在源字符串中查找目标串的位置，要求：
1，使用回溯法；
伪代码：
输入：主串S，模式T
输出：T在S中的位置
1.初始化主串比较的开始位置index=0；
2.在串S和串T中设置比较的起始下标i=0，j=0;
3.重复下述操作，直到S或T的所有字符均比较完毕：
3.1如果S[i]等于T[j]，则继续比较S和T的下一对字符；
3.2否则，下一趟匹配的开始位置index++，回溯下标i=index，j=0；
4.如果T中所有字符均比较完，则返回匹配的开始位置index；否则返回0；
算法主体：

测试用例：

运行结果：

2，程序实现KMP算法，在算法实现过程中说明辅助数据结构next数组的作用；
伪代码：
输入：主串S，模式T
输出：T在S中的位置
1.在串S和串T中分别设置比较的起始下标i=0，j=0；
2.重复下述操作，直到S或T的所有字符均比较完毕：
2.1如果S[i]等于T[j]，则继续比较S和T的下一对字符；
2.2否则，将下标j回溯到next[j]位置，即j=next[j]；
2.3如果j等于-1，则将下标i和j分别加1，准备下一趟比较；
3.如果T中所有字符均比较完毕，则返回本趟匹配的开始位置；否则返回0；
算法主体：


测试用例：

运行结果：

next数组作用：
个人观点：求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。
3，定性分析回溯法和KMP算法的时间复杂度；
回溯法：
设主串S长度为n，模式T长度为m，在匹配成功的情况下，考虑最坏情况，即每趟不成功的匹配都发生在模式T的最后一个字符。
设匹配成功发生在处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此平均比较次数是：

一般情况下，m<<n，因此最坏情况下的时间复杂性是O(n×m)。
KMP算法：
在求得模式T的next值后，KMP算法只需将主串扫描一遍，设主串的长度为n，则KMP算法的时间复杂性是O(n)。
4，在以上基础上阐述KMP算法相对于回溯法的优越性；
回朔法：方法粗暴，因为每次查找失败，源串需要回到起始位置的下一个位置开始查找，所以该算法算法复杂度大，很浪费时间。
KMP算法：先对要查找的字符串进行分析，找出其中重复的子字符串。然后将目标串与源串比较，一旦比较失败，则不用回朔，而是根据目标串子串的重复情况，直接调到重复子串的下一个位置。这样减少了大量的回朔，算法复杂度大量减小。
5，课堂拓展：求字符串S1和S2的最大公共子串。
思路：
1.输入两个字符串，由短字符串的长度决定比较次数。
2.每次比较一个字符，从短字符串的第一个依次与长字符串的每一个字符比较，若出现相同的字符，则两个字符串各自取下一位进行比较，直到出现不相同字符的为止。（同时要注意比较是不能超出短字符串的长度，不然会出现未知后果）
3.定义两个数组a，b；a用来获取相同字符，若a的长度大于b的长度，则将a复制给b。
算法代码部分：

主函数测试用例：

运行结果：