#include<iostream>
using namespace std;

//KMP算法 之我觉得自己说得很好懂
//https://www.jianshu.com/p/c372a287ba79
unsigned  long getNext(string maxStr) {
	//保存字符串的长度
	unsigned  long length = maxStr.size();
	string str1;
	string str2;
	int subLen = 0;
	for (int i = 1 ; i < length; ++i) {
		//截取两段字符串
		str1 = maxStr.substr(0,i);
		str2 = maxStr.substr(length-i,length);
		if(str2 == str1) {
			//比较
			subLen = i;
		}
	}
	return length - subLen;
}

int main() {
	/*
	 目标字符串:asabusakswwlsaksaksawlsdkiis
	 匹配字符串:saksawl
	 */
	string deStr("asabusakswwlsaksaksawlsdkiis");
	string keyStr("saksawl");
	//1.先匹配,找到匹配到的最大字符串,需要一个字符串maxStr来保存
	string maxStr("");
	unsigned long steps;
	int length; //用于循环中计算当前长度
	//2.开始匹配
	for (int i = 0; i < (deStr.size() - keyStr.size());) {
		length = 0;//每次重新搜索都把length置0
		steps = 1;//每次平移一段距离都重新计算平移的距离
		for (int j = i; j < (keyStr.size() + i); ++j) {
			if (deStr.at(j) != keyStr.at(j-i)) {
				if ( length > 1) {
					maxStr = keyStr.substr(0,length);
					steps = getNext(maxStr); //这里需要一个函数,来告诉我们每次需要跳过多少次
				}
				break;  //如果当前循环不一致则结束循环
			}
			++length; //匹配成功字符串长度加1
			if (length == keyStr.size()) {
				cout << "匹配成功" << endl;
				return 0;
			}
		}
		i += steps;
	}
	cerr << "匹配不成功";
	return -1;
}