Cod sursa(job #629504)

Utilizator matemariaescuMaria Mateescu matemariaescu Data 3 noiembrie 2011 14:14:56
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
# include <fstream>
# include <string>
# define PRIM 777737

using namespace std;

string A,B;
int baza,i,j,a,b,put,pos;
int inc[1011];
int v[200];

int trebe (char x)
{
	if (x<='Z'&&x>='A')
		return 1;
	if (x<='z'&&x>='a')
		return 1;
	if (x<='9'&&x>='0')
		return 1;
	return 0;
}

int verifica (int j)
{
	int i;
	for (i=j;i<j+B.length();i++)
		if (B[i-j]!=A[i])
			return 0;
	return 1;
}

int main ()
{
	ifstream fin ("strmatch.in");
	ofstream fout ("strmatch.out");
	fin>>B;
	fin>>A;
	baza=67;
	j=0;
	put=1;
	a=0;
	for (i=1;i<=123;i++)
		if (trebe((char)i))
			v[i]=j,j++;
	for (i=0;i<B.length();i++)
	{	
		b=(b*baza+v[B[i]])%PRIM;
		put=(put*baza)%PRIM;
		a=(a*baza+v[A[i]])%PRIM;
	}
	
	if (a==b)
	{
		if (verifica(0))
			pos++,inc[pos]=0;
	}
	for (i=B.length();i<A.length();i++)
	{
		a=((a*baza+v[A[i]])%PRIM - (put*v[A[i-B.length()]])%PRIM +PRIM)%PRIM;
		
		if (a==b)
			if (verifica(i-B.length()+1))
			{pos++; if (pos<=1000)inc[pos]=i-B.length()+1;}
	}
	fout<<pos<<'\n';
	for (i=1;i<=1000&&i<=pos;i++)
		fout<<inc[i]<<' ';
	fout<<'\n';
	return 0;
}