Cod sursa(job #547211)

Utilizator feelshiftFeelshift feelshift Data 5 martie 2011 23:41:35
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
// http://infoarena.ro/problema/strmatch
#include <fstream>
#include <string>
using namespace std;

#define maxSize 2000002
#define maxAnswers 1002

ifstream in("strmatch.in");
ofstream out("strmatch.out");

int matches;
int indexx[maxAnswers];
int lengthA,lengthB;
int pi[maxSize];
string A,B;

void makePrefix();

int main() {
	in >> A >> B;
	
	lengthA = A.size();
	lengthB = B.size();
	lengthA--;
	lengthB--;

	makePrefix();

	//for(int i=0;i<=lengthA;i++)
		//out << pi[i] << " ";

	int q = 0;
	for(int i=0;i<=lengthB;i++) {
		while(q && A[q] != B[i])
			q = pi[q];

		if(A[q] == B[i])
			q++;
		
		if(q == lengthA + 1) {
			q = pi[lengthA];
			indexx[++matches] = i - lengthA;
		}
	}

	out << matches << "\n";
	int stop = min(matches,1000);
	for(int i=1;i<=stop;i++)
		out << indexx[i] << " ";
	
	in.close();
	out.close();

	return (0);
}

void makePrefix() {
	int q = 0;

	for(int i=2;i<=lengthA;i++) {
		while(q && A[q] != A[i])
			q = pi[q];
		
		if(A[q] == A[i])
			q++;

		pi[i] = q;
	}
}