本地运行无问题,但是提交就RE 记录
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string stringMain;
string stringMatch;
vector<int>prefixMatch;
vector<int> MatchStr_KMP(string&mainStr, string&matchStr,
vector<int>&matchStr_next) {
vector<int>matchPosition;
matchPosition.clear();
int matchPosition_mainStr = 0;
int matchPosition_matchStr = 0;
int length_mainStr = mainStr.length();
int length_matchStr = matchStr.length();
while (matchPosition_mainStr < length_mainStr) {
while (matchPosition_matchStr >= 0 &&
matchStr[matchPosition_matchStr + 1] !=
mainStr[matchPosition_mainStr + 1]) {
matchPosition_matchStr =
matchStr_next[matchPosition_matchStr] - 1;
}
if (matchStr[matchPosition_matchStr + 1] ==
mainStr[matchPosition_mainStr + 1]) {
matchPosition_matchStr++;
}
matchPosition_mainStr++;
if (matchPosition_matchStr == length_matchStr - 1) {
matchPosition.push_back
(matchPosition_mainStr - length_matchStr + 2);
matchPosition_matchStr =
matchStr_next[matchPosition_matchStr] - 1;
}
}
return matchPosition;
}
vector<int> MatchNext_KMP(string &matchingStr) {
vector<int>next_KMP;
int length_matchingStr = matchingStr.length();
next_KMP.assign(length_matchingStr, 0);
int prefixPointer = -1, suffixPointer = 0;
while (suffixPointer < length_matchingStr) {
while (prefixPointer >= 0 &&
matchingStr[prefixPointer + 1] !=
matchingStr[suffixPointer + 1]) {
prefixPointer = next_KMP[prefixPointer] - 1;
}
if (matchingStr[prefixPointer + 1] ==
matchingStr[suffixPointer + 1]) {
prefixPointer++;
}
next_KMP[++suffixPointer] = prefixPointer + 1;
}
return next_KMP;
}
int main() {
getline(cin, stringMain);
getline(cin, stringMatch);
prefixMatch = MatchNext_KMP(stringMatch);
vector<int>allPosition =
MatchStr_KMP(stringMain, stringMatch, prefixMatch);
for (int i = 0, length = allPosition.size(); i < length; i++) {
cout << allPosition[i] << "\n";
}
for (int i = 0, length = prefixMatch.size(); i < length; i++) {
cout << prefixMatch[i] << " ";
}
return 0;
}