P3375 【模板】KMP字符串匹配

R50999536 记录详情

#include <vector>
#include <string>
#include <iostream>
using namespace std;

int pi(vector<int> s, int i) {
	s.resize(i + 1);
	int k = s.size() - 1;
	vector<int>::iterator prefix_head = s.begin();
	vector<int>::iterator prefix_tail = s.end();
	vector<int>::iterator postfix_head = s.begin();
	vector<int>::iterator postfix_tail = s.end();
	prefix_tail--;
	postfix_head++;
	while(k >= 0) {
		vector<int> prefix(prefix_head, prefix_tail);
		vector<int> postfix(postfix_head, postfix_tail);
		if(prefix == postfix) {
			return k;
		}
		prefix_tail--;
		postfix_head++;
		k--;
	}
	return 0;
}

class KMP {

	private :
		int _alphabat_size = 26;
		int _vertex_size;
		vector<vector<int> > _delta_table;

		void _restart() {
			_delta_table.resize(_vertex_size);
			for(int i = 0; i < _vertex_size; i++) {
				_delta_table[i].resize(_alphabat_size);
			}
		}

		int _delta(int q, int alpha) {
			return _delta_table[q][alpha];
		}

	public :
		KMP(int size) {
			_vertex_size = size;
		}

		~KMP() {
			;
		}

		void build(vector<int> p) {
			_vertex_size = p.size() + 1;
			_restart();

			for(int q = 0; q < _vertex_size; q++) {
				for(int alpha = 0; alpha < _alphabat_size; alpha++) {
					if(q + 1 < _vertex_size && alpha == p[q]) {
						_delta_table[q][alpha] = q + 1;
					} else if(q == 0 && alpha != p[0]) {
						_delta_table[q][alpha] = 0;
					} else if(q > 0 && alpha != p[q]) {
						_delta_table[q][alpha] =
						    _delta_table[pi(p, q - 1)][alpha];
						    //cout << q << " " << pi(p, q - 1) << endl;
					}
					//cout << _delta_table[q][alpha] << " ";
				}
				//cout << endl;
			}
		}

		bool test(vector<int> s) {
			int q = 0;
			for(int i = 0; i < (int)s.size(); i++) {
				//cout << "index : " << i << ";";
				//cout << "vertex : " << q << ";" << endl;
				q = _delta(q, s[i]);
				if(q == _vertex_size - 1) {
					cout << i + 3 - _vertex_size << endl;
				}
			}
			return q == _vertex_size - 1;
		}

		void debug() {
			for(int i = 0; i < _vertex_size; i++){
				for(int j = 0; j < _alphabat_size; j++){
					cout << _delta_table[i][j] << " ";
				}
				cout << endl;
			}
		}
};

void read(vector<int>& s, vector<int>& p) {
	string t;
	cin >> t;
	for(int i = 0; i < (int)t.length(); i++) {
		s.push_back(t[i] - 'A');
	}
	cin >> t;
	for(int i = 0; i < (int)t.length(); i++) {
		p.push_back(t[i] - 'A');
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	vector<int> s;
	vector<int> p;
	KMP body(26);

	read(s, p);

	body.build(p);
	
//	body.debug();
	
	body.test(s);
//
	for(int i = 0; i < (int)p.size(); i++) {
		cout << pi(p, i) << " ";
	}
	cout << endl;
	return 0;
}

已经调了半天了，若各位能帮帮忙将感激不尽qwq