Cod sursa(job #632867)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 12 noiembrie 2011 14:33:48
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#define B 67
#define P 666013
using namespace std;
int a[130];
int alfabet(char c)
{
	if (('a'<=c)&&(c<='z'))
		return 1;
	if (('A'<=c)&&(c<='Z'))
		return 1;
	if (('0'<=c)&&(c<='9'))
		return 1;
	return 0; 
}//alfabet
int main()
{
	string pattern, text;
	unsigned long n, i, j, p, t, putere;
	int nrSol;
	vector<int> sol;
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	j=0;
   for (i=1; i<123; i++)
		if (alfabet((char)i))
			a[i]=j++;
	fin>>pattern>>text;
	p=0;
	t=0;
	putere=1;
	n=pattern.length();
	for (i=0; i<n; i++)
	{
		p=(p*B+a[(int)pattern[i]])%P;
		t=(t*B+a[(int)text[i]])%P;
		putere*=B;
	}//for i
	putere/=B;
	nrSol=0;
   for (i=n; i<text.length(); i++)
	{
		t=(t-a[(int)text[i-n]]*putere+P)%P;
		t=(t*B)%P;
		t=(t+a[(int)text[i]])%P;
		if (t==p)
		{
			if (sol.size()<1000)
				sol.push_back(i-n+1);
			nrSol++;
		}//if
	}//for i
	fout<<sol.size()<<"\n";
	for (i=0; i<sol.size(); i++)
		fout<<sol[i]<<" ";
	return 0;
}//main