本地AC提交RE
查看原帖
本地AC提交RE
297831
idgg007楼主2022/8/27 10:52

本地运行无问题,但是提交就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;
}
2022/8/27 10:52
加载中...