Cod sursa(job #1070964)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 2 ianuarie 2014 13:22:02
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

string a,b;

class StrMatcher {

public:
	StrMatcher() :
		m(-1)
		{
			T.resize(a.size()+1,0);
			computePartialMatchTable();
		}
	int getNextPos();

private:
	void computePartialMatchTable();
	
	int m;

	vector<int> T;// Partial match table
};

void StrMatcher::computePartialMatchTable() {
	int pos = 2;// current position that we are computing in t
	int cnd = 0;// where in W is the next character of the current candidate
	T[0]=-1; T[1]=0;

	while(pos < a.size()) {
		if(a[pos-1] == a[cnd]) {
			cnd++;
			T[pos]=cnd;
			pos++;
		}
		else if(cnd > 0) 
			cnd = T[cnd];
		else {
			T[pos]=0;
			pos++;
		}
	}
}

int StrMatcher::getNextPos() {
	m++;
	int i = 0;
	while(m + i < b.size()) {
		if(a[i] == b[m+i]) {
			i++;
			if(i == a.size()) {
				return m;
			}
		}
		else {
			m += i - T[i];
			if(T[i] > -1) 
				i = T[i];
			else
				i = 0;
		}
	}

	return -1;
}

int main() {
	a.reserve(2000002);
	b.reserve(2000002);

	in >> a >> b;

	if(a.size()>b.size()){
		out << "0\n";
		return 0;
	}

	StrMatcher match;

	vector<int> sol(1000,0);
	int pos = match.getNextPos();
	size_t n = 0;
	while(pos != -1) {
		if(n<1000)
			sol[n]=pos;
		n++;
		pos = match.getNextPos();
	} 

	out << n << '\n';
	for(size_t i = 0, l = min(n,1000u); i < l; ++i) {
		out << sol[i] << ' ';
	}
	out << '\n';
	return 0;
}