kmp 算法 + 递归算法

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

using namespace std;
const int N = 1005;
int n;
string str[N];
vector<string> p;

vector<string> getp(string tmp){
	int s, e;
	vector<string> pp;
	s = tmp.find("[");
	if(s == string::npos){
		pp.push_back(tmp);
	} else {
		e = tmp.find("]");
		for(int i = s+1; i < e; i++){
			string x = tmp.substr(0,s) + tmp.substr(i,1) + tmp.substr(e+1, tmp.size() - e - 1);
			if(x.find("[") != string::npos){
				vector<string> re = getp(x);
				for(int i = 0; i < re.size(); i++) pp.push_back(re[i]);
			} else {
				pp.push_back(" " + x);
			}
		}
	}
	return pp;
}
int main()
{
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> str[i];
		str[i].insert(0, " ");
	}
	string tmp;
	cin >> tmp;
	p = getp(tmp);

	// next
	vector<vector<int>> next;
	for(int i = 0; i < p.size();i++){
		vector<int> a;
		a.push_back(0); a.push_back(0);
		string pp = p[i];
		for(int i = 0; i < pp.size(); i++){
			if(pp[i] >= 'A' && pp[i] <= 'Z') pp[i] -= 'A' - 'a';
		}
		for(int j = 2, k = 0; j < pp.size(); j++){
			while(k && pp[j] != pp[k+1]) k = a[k];
			if(pp[j] == pp[k+1]) k++;
			a.push_back(k);
		}
		next.push_back(a);
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < p.size(); j++){
			string ss = str[i];
			for(int i = 0; i < ss.size(); i++){
				if(ss[i] >= 'A' && ss[i] <= 'Z') ss[i] -= 'A' - 'a';
			}
			string pp = p[j];
			for(int i = 0; i < pp.size(); i++){
				if(pp[i] >= 'A' && pp[i] <= 'Z') pp[i] -= 'A' - 'a';
			}
			for(int ii = 1, jj = 0; ii < ss.size(); ii++){
				while(jj && pp[jj+1] != ss[ii]) jj = next[j][jj];
				if(pp[jj+1] == ss[ii]) jj++;
				if(jj == pp.size()-1){
					cout << i+1 << " " << str[i].substr(ii-jj+1, jj) << endl;
				}
			}
		}
	}

	return 0;
}