Cod sursa(job #696732)

Utilizator cdascaluDascalu Cristian cdascalu Data 28 februarie 2012 19:50:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<vector>
#include<cstring>
#define Nmax 2000005
using namespace std;
char a[Nmax],b[Nmax];
int pi[Nmax],N,M;
void prefix()
{
	int k=0,i;
	pi[1] = 0;
	
	for(i=2;i<=N;++i)
	{
		while(k>0 && a[k+1] != a[i])
			k = pi[k];
		if(a[k+1] == a[i])
			k = k+1;
		pi[i] = k;
	}
}
int main()
{
	FILE*f = fopen("strmatch.in","r");
	fscanf(f,"%s %s",a,b);
	fclose(f);
	
	int k=0,i;
	
	N = strlen(a);
	M = strlen(b);
	
	for(i=M;i>0;--i)b[i] = b[i-1];
	for(i=N;i>0;--i)a[i] = a[i-1];
	
	prefix();
	vector<int> pos;
	for(i=1;i<=M;++i)
	{
		while(k>0 && a[k+1] != b[i])
			k = pi[k];
		if(a[k+1] == b[i])
			k = k+1;
		if(k == N)
			pos.push_back(i-N+1);
	}
	FILE*g = fopen("strmatch.out","w");
	fprintf(g,"%d\n",pos.size());
	k=0;
	for(vector<int>::iterator it = pos.begin();it!=pos.end() && k<1000;++it)
	{
		fprintf(g,"%d ",*it-1);
		++k;
	}
	fclose(g);
	return 0;
}