Pagini recente » Cod sursa (job #1001535) | Cod sursa (job #985552) | Cod sursa (job #1140639) | Cod sursa (job #230058) | Cod sursa (job #868783)
Cod sursa(job #868783)
// am citit problema la ora : 4:55 P.M. , Data : azi Anu : asta :)
// Visane, daca te uiti la sursa mea, lumineaza-ne :)!
// PS : ti-am zis-o :)) !
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std;
FILE*in=fopen("strmatch.in","r");
FILE*out=fopen("strmatch.out","w");
int constant,compare,pozitie,contor_afisat,constant2,compare2,hareza2=1;
int hareza=1; // numarul ala 73 la a n-1
char a[2000001], b[2000001];
vector<int> contor_afisa;
int main()
{
fscanf(in,"%s",a);
int ceva=strlen(a);
fscanf(in,"%s",b);
int altceva=strlen(b);
compare=a[0]%20021;
compare2=a[0]%20007;
constant=b[0]%20021;
constant2=b[0]%20007;
for(int i=1;i<ceva;++i)
{
compare*=73;
compare+=a[i];
compare%=20021;
compare2=(compare2*73+a[i])%20007;
constant*=73;
constant+=b[i];
constant%=20021;
constant2=(constant2*73+b[i])%20007;
hareza*=73;
hareza%=20021;
hareza2*=73;
hareza2%=20007;
}
if(compare==constant && compare2==constant2)
{
contor_afisat++;
contor_afisa.push_back(-1);
}
for(int i=ceva;i<=altceva;++i)
{
int ajutor,ajutor2;
ajutor=((hareza*b[i-ceva])%20021);
ajutor2=((hareza2*b[i-ceva])%20007);
constant-=ajutor;
constant+=20021;
//constant%=20021;
constant*=73;
constant+=b[i];
constant%=20021;
constant2-=ajutor2;
constant2+=20007;
//constant2%=20007;
constant2*=73;
constant2+=b[i];
constant2%=20007;
if(compare==constant && compare2==constant2)
{
if(contor_afisat++ < 1000)
contor_afisa.push_back(i-ceva);
}
}
fprintf(out,"%d\n",contor_afisat);
for(int i=0;i<(int)contor_afisa.size();++i)
fprintf(out,"%d ",contor_afisa[i]+1);
fclose(in);
fclose(out);
}