Cod sursa(job #1070531)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 1 ianuarie 2014 14:53:58
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

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

class StrMatcher {

public:
	StrMatcher(const string &_W, const string &_S) : 
		S(_S),
		W(_W),
		m(-1)
		{
			computePartialMatchTable();
		}
	int getNextPos();

private:
	void computePartialMatchTable();
	
	int m,i;

	string S;// The string in which we search
	string W;// The string that is searched
	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.resize(W.size()+1,0);
	T[0]=-1; T[1]=0;

	while(pos < W.size()) {
		if(W[pos-1] == W[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 < S.size()) {
		if(W[i] == S[m+i]) {
			i++;
			if(i == W.size()) {
				return m;
			}
		}
		else {
			m += i - T[i];
			if(T[i] > -1) 
				i = T[i];
			else
				i = 0;
		}
	}

	return -1;
}

int main() {
	string a,b;

	in >> a >> b;

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

	StrMatcher match(a,b);

	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;
}