Cod sursa(job #879643)

Utilizator howsiweiHow Si Wei howsiwei Data 15 februarie 2013 18:27:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	string a, s;
	fin >> a >> s;
	int maxmatch[a.length()];// store last index of longest substring that is both prefix and suffix
	maxmatch[0]=-1;
	for (size_t i=1; i<a.length(); ++i) {
		int best=maxmatch[i-1];
		while (true) {
			if (a[best+1]==a[i]) {
				++best;
				break;
			}
			if (best==-1) break;
			best=maxmatch[best];
		}
		maxmatch[i]=best;
	}
	//for (size_t i=0; i<a.length(); ++i) fout << maxmatch[i] << ' '; fout << '\n';
	int best=-1;
	vector<int> last;
	for (size_t i=0; i<s.length(); ++i) {
		while (true) {
			if (a[best+1]==s[i]) {
				++best;
				if (best==int(a.length())-1) {
					last.push_back(i);
					best=maxmatch[best];
				}
				break;
			}
			if (best==-1) break;
			best=maxmatch[best];
		}
	}
	fout << last.size() << '\n';
	int num=min(int(last.size()),1000);
	for (int i=0; i<num; ++i)
		fout << last[i]-a.length()+1 << ' ';
	return 0;
}