题解 | #字符串匹配#

改进型KMP

// E4-6 字符串匹配

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int Next[100] = { 0 };

bool IsMatch(char a, char b) {
	return a == b || abs(a - b) == abs('a' - 'A');
}

void GetNext(string pattern) {
	int m = pattern.size();
	int j = 0;
	Next[j] = -1;
	int i = Next[j];
	while (j < m) {
		if (i == -1 || IsMatch(pattern[j], pattern[i])) {
			i++;
			j++;
			Next[j] = i;
		}
		else {
			i = Next[i];
		}
	}
}

int KMP(string text, string pattern, string uni) {
	int m = pattern.size();
	int n = text.size();
	int num = 0;
	GetNext(pattern);
	int i = 0, j = 0;
	while (i < n && j < m) {
		if (j != -1 && pattern[j] == '#') {
			for (int k = 0; k < uni.size(); k++) {
				if (IsMatch(text[i], uni[k])) {
					i++;
					j++;
					break;
				}
			}
		}
		else if (j == -1 || IsMatch(text[i], pattern[j])) {
			i++;
			j++;
		}
		else {
			j = Next[j];
		}

	}
	if (j == m) {
		return i - j;
	}
	else {
		return -1;
	}
}

void Process(string s, string& s1, string& uni) {
	int flag = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '[') {
			flag = 1;
			s1.insert(s1.end(), '#');
			continue;
		}
		if (s[i] == ']') {
			flag = 0;
			continue;
		}
		if (flag == 0) {
			s1.insert(s1.end(), s[i]);
		}
		else {
			uni.insert(uni.end(), s[i]);
		}
	}
}

int main()
{
	int n;
	while (cin >> n) {
		vector<string> texts;
		while (n--) {
			string s;
			cin >> s;
			texts.push_back(s);
		}
		string str, pattern, uni;
		cin >> str;
		Process(str, pattern, uni);
		for (int i = 0; i < texts.size(); i++) {
			int index = KMP(texts[i], pattern, uni);
			if (index != -1) {
				cout << i + 1 << ' ' << texts[i].substr(index, pattern.size()) << endl;
			}
		}
	}

}