1、某个位置前面最长前缀和最长后缀的匹配长度：

限定：前缀不能包含最后一个字符，后缀不能包含第一个字符。

字符串 "abcabcd" 的最长前缀和最长后缀匹配的长度为3。当前缀和后缀取1的时候，前缀为a，后缀为c，不匹配；当前缀和后缀取2的时候，前缀ab，后缀bc，不匹配；前缀和后缀取3，前缀abc，后缀abc，匹配，那它是否最长的匹配长度? 继续看，前缀和后缀为4，前缀 abca，cabc，不匹配；取5，前缀abcab，后缀 bcabc，不匹配；取6，前缀abcabc最后一个c取到后缀，超出限定，舍弃，停止，所以最长前缀和最长后缀的最长匹配就是3，匹配字符为abc.

2、next数组。next数组记录的就是字符串当前某个字符前面的匹配信息，所以next数组和该字符串长度相等。比如遍历字符串 "abcabcd"，字符串第一个位置a，作为第一个字符，a前面没有所谓的前缀和后缀，规定其位置在next数组的元素为-1；第二个位置b，其前面只有一个字符，而限定中说到前缀不能取到后缀，所以规定其在next数组的位置为0；第三个位置其前缀为a，后缀为b，不匹配，为0；第四个位置a，，没有匹配的前后缀，为0；第五个位置b，匹配的只有前缀a和后缀a；第六个位置c，匹配的是前缀ab和后缀ab，所以为2，第7个位置匹配的是abc，为3。所以该字符串的next数组为【-1 0 0 0 1 2 3】

实现思路：

 

代码实现：

#include<iostream>
#include<string>
using namespace std;
int* getNextArray(string str2) {
	if (str2.length() == 1) {
		int* next = new int[1];
		next[0] = -1;
		return next;
	}
	int* next = new int[str2.length()];
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int cn = 0;//当i=2的时候，下面比较的时候是1位置与0位置是否相等，所以cn从0开始
	while (i < str2.length()) {
		if (str2[i - 1] == str2[cn]) { //考虑i-1位置与cn位置是否相等，如果相等则当前位置的next数组元素为cn+1
			next[i++] = ++cn;
		}
		else if (cn > 0) {//还可以往前跳，cn会跳到当前当前cn的next数组元素位置，完成cn的更新
			cn = next[cn];
		}
		else {
			next[i++] = 0;//无法跳了。
		}
	}
	//退出循环意味着数组已经填完了，
	return next;
}

3、匹配过程。

目标：在str1中找是否存在str2子串

第一步：i1指向str1首字符，i2指向str2首字符，如果i1字符和i2字符相等，则i1++，i2++

第二步：不等，没配上，则判断i2的next数组元素是否为-1，如果是则i2处于首字符位置，此时只需要i1++

第三步：如果i2的next数组元素不为-1，不是首字符位置，则i2位置应该跳当前next数组位置再往下匹配

第四步：如果i2遍历完了str2说明匹配上了否则返回-1

代码：

int getIndexOf(string str1, string str2) {
	if (str1.length() == 0 || str2.length() == 0)
		return -1;
	int i1 = 0;//str1
	int i2 = 0;//str2
	int* next = getNextArray(str2);//求解next数组
	while (i1 < str1.length() && i2 < str2.length()) {
		if (str1[i1] == str2[i2]) {
			i1++;
			i2++;
		}
		else {//没配上，往前跳
			//如果当前i2位置的next数组位置值为-1表明i2在第一个位置，没得跳，第一个位置都没配上，i1++
			if (next[i2] == -1) {
				i1++;
			}
			else {
				i2 = next[i1];//跳到next数组中那个位置
			}
		}
	}
	return i2 == str2.length() ? i1 - i2 : -1;
}

 完整测试代码：

#include<iostream>
#include<string>
using namespace std;
int* getNextArray(string str2) {
	if (str2.length() == 1) {
		int* next = new int[1];
		next[0] = -1;
		return next;
	}
	int* next = new int[str2.length()];
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int cn = 0;//当i=2的时候，下面比较的时候是1位置与0位置是否相等，所以cn从0开始
	while (i < str2.length()) {
		if (str2[i - 1] == str2[cn]) { //考虑i-1位置与cn位置是否相等，如果相等则当前位置的next数组元素为cn+1
			next[i++] = ++cn;
		}
		else if (cn > 0) {//还可以往前跳，cn会跳到当前当前cn的next数组元素位置，完成cn的更新
			cn = next[cn];
		}
		else {
			next[i++] = 0;//无法跳了。
		}
	}
	//退出循环意味着数组已经填完了，
	return next;
}
int getIndexOf(string str1, string str2) {
	if (str1.length() == 0 || str2.length() == 0)
		return -1;
	int i1 = 0;//str1
	int i2 = 0;//str2
	int* next = getNextArray(str2);//求解next数组
	while (i1 < str1.length() && i2 < str2.length()) {
		if (str1[i1] == str2[i2]) {
			i1++;
			i2++;
		}
		else {//没配上，往前跳
			//如果当前i2位置的next数组位置值为-1表明i2在第一个位置，没得跳，第一个位置都没配上，i1++
			if (next[i2] == -1) {
				i1++;
			}
			else {
				i2 = next[i2];//跳到next数组中那个位置
			}
		}
	}
	return i2 == str2.length() ? i1 - i2 : -1;
}

int main() {
	string s1, s2;
	while (cin >> s1 >> s2) {
		cout << getIndexOf(s1, s2);
	}
	return 0;
}