You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
59 lines
1.4 KiB
59 lines
1.4 KiB
#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;
|
|
}
|
|
|