Cod sursa(job #499253)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 9 noiembrie 2010 12:58:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<string.h>
#include<vector>

using namespace std;


#define pb push_back  

vector <int> v;
vector <int> :: iterator it;

int pi[2000005];

char a[2000005],b[2000005];


int main()
{
	int i,sw,n,m;
	
	ifstream f("strmatch.in");
	f>>a>>b;
	n=strlen(a);
	m=strlen(b);
	
	pi[0]=0;
	for (i=1;i<n;i++)
	{
		sw=pi[i-1];
		while (sw>0 && a[i]!=a[sw])
			sw=pi[sw-1];
		if (a[i]==a[sw])
			pi[i]=sw+1;
		else
			pi[i]=0;
	}
	
	
	
	sw=0;
	for (i=0;i<m;i++)
	{
		while (sw>0 && b[i]!=a[sw])
			sw=pi[sw-1];
		if (b[i]==a[sw])
			sw++;
		if (sw==n)
		{
			sw=pi[sw-1];
			if (v.size()<1000) v.pb(i+1-n) ;
		}
	}
	
	ofstream g("strmatch.out");
	g<<v.size()<<'\n';
	
	for (it=v.begin();it<v.end();++it)
		g<<*it<<' ';
	
	f.close();
	g.close();
	return 0;
}