Cod sursa(job #964072)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 20 iunie 2013 00:21:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

vector<int>qq;
int uu[200013], nr;
string pp, ss;

void pat(){
	int k,l = pp.length();
	uu[0]=k=-1;
	for(int i=1;i<l;i++)
	{
		while(k>-1 && pp[i] != pp[k+1])k = uu[k];
		if(pp[i]==pp[k+1])k++;
		uu[i]=k;
	}
	//for(int i=0;i<l;i++) cout << uu[i] << " ";
	//cout << endl;
}

void mat(){
	int k, l1 = pp.length(), l2 = ss.length();
	k=-1;
	for(int i=0;i<l2;i++)
	{
		while(k>-1 && ss[i] != pp[k+1])k=uu[k];
		if(ss[i] == pp[k+1])k++;
		if(k==l1-1)
		{
			if(nr<1000) qq.push_back(i-l1+1);
			nr++;
			k=uu[k];
		}
	}
	g << qq.size() << endl;
	l1 = qq.size();
	for(int i=0;i<l1;i++)
	g << qq[i] << " ";
}

int main(){
	f >> pp >> ss;
	pat();
	mat();	
	return 0;
}