|
|
|
|
|
#include<iostream>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
|
|
|
//KMP<4D>㷨 ֮<>Ҿ<EFBFBD><D2BE><EFBFBD><EFBFBD>Լ<EFBFBD>˵<EFBFBD>úܺö<DCBA>
|
|
|
|
|
|
//https://www.jianshu.com/p/c372a287ba79
|
|
|
|
|
|
unsigned long getNext(string maxStr) {
|
|
|
|
|
|
//<2F><><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD><EFBFBD>ij<EFBFBD><C4B3><EFBFBD>
|
|
|
|
|
|
unsigned long length = maxStr.size();
|
|
|
|
|
|
string str1;
|
|
|
|
|
|
string str2;
|
|
|
|
|
|
int subLen = 0;
|
|
|
|
|
|
for (int i = 1 ; i < length; ++i) {
|
|
|
|
|
|
//<2F><>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD>
|
|
|
|
|
|
str1 = maxStr.substr(0,i);
|
|
|
|
|
|
str2 = maxStr.substr(length-i,length);
|
|
|
|
|
|
if(str2 == str1) {
|
|
|
|
|
|
//<2F>Ƚ<EFBFBD>
|
|
|
|
|
|
subLen = i;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return length - subLen;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
/*
|
|
|
|
|
|
Ŀ<EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><EFBFBD><EFBFBD>:asabusakswwlsaksaksawlsdkiis
|
|
|
|
|
|
ƥ<EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><EFBFBD><EFBFBD>:saksawl
|
|
|
|
|
|
*/
|
|
|
|
|
|
string deStr("asabusakswwlsaksaksawlsdkiis");
|
|
|
|
|
|
string keyStr("saksawl");
|
|
|
|
|
|
//1.<2E><>ƥ<EFBFBD><C6A5>,<2C>ҵ<EFBFBD>ƥ<EFBFBD>䵽<EFBFBD><E4B5BD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD>,<2C><>Ҫһ<D2AA><D2BB><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD>maxStr<74><72><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|
|
|
|
|
string maxStr("");
|
|
|
|
|
|
unsigned long steps;
|
|
|
|
|
|
int length; //<2F><><EFBFBD><EFBFBD>ѭ<EFBFBD><D1AD><EFBFBD>м<EFBFBD><D0BC>㵱ǰ<E3B5B1><C7B0><EFBFBD><EFBFBD>
|
|
|
|
|
|
//2.<2E><>ʼƥ<CABC><C6A5>
|
|
|
|
|
|
for (int i = 0; i < (deStr.size() - keyStr.size());) {
|
|
|
|
|
|
length = 0;//ÿ<><C3BF><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>length<74><68>0
|
|
|
|
|
|
steps = 1;//ÿ<><C3BF>ƽ<EFBFBD><C6BD>һ<EFBFBD>ξ<EFBFBD><CEBE>붼<EFBFBD><EBB6BC><EFBFBD>¼<EFBFBD><C2BC><EFBFBD>ƽ<EFBFBD>Ƶľ<C6B5><C4BE><EFBFBD>
|
|
|
|
|
|
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); //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫһ<D2AA><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>,<2C><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ÿ<EFBFBD><C3BF><EFBFBD><EFBFBD>Ҫ<EFBFBD><D2AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ٴ<EFBFBD>
|
|
|
|
|
|
}
|
|
|
|
|
|
break; //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǰѭ<C7B0><D1AD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѭ<EFBFBD><D1AD>
|
|
|
|
|
|
}
|
|
|
|
|
|
++length; //ƥ<><C6A5><EFBFBD>ɹ<EFBFBD><C9B9>ַ<EFBFBD><D6B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȼ<EFBFBD>1
|
|
|
|
|
|
if (length == keyStr.size()) {
|
|
|
|
|
|
cout << "ƥ<EFBFBD><EFBFBD><EFBFBD>ɹ<EFBFBD>" << endl;
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
i += steps;
|
|
|
|
|
|
}
|
|
|
|
|
|
cerr << "ƥ<EFBFBD>䲻<EFBFBD>ɹ<EFBFBD>";
|
|
|
|
|
|
return -1;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
