Cod sursa(job #1838084)

Utilizator vancea.catalincatalin vancea.catalin Data 30 decembrie 2016 23:27:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<fstream>
#include<string>
#define B1 40
#define B2 50
#define M1 4500000000
#define M2 1000000000
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
long long p1=1,p2=1,k1,k2,k3,k4;
int poz[1111];
int main()
{
    int i,ante,j,n=0;
    fin>>a>>b;
    for(i=0;i<a.size();i++)
    {
        if(i>0) p1=(p1*B1)%M1;
        k1=(k1*B1+(a[i]-'A'+1))%M1;
    }
    for(i=0;i<a.size();i++)
    {
        k2=(k2*B1+(b[i]-'A'+1))%M1;
    }
    if(k1==k2)
    {
        n++;
        poz[n]=0;
    }
    for(i=a.size();i<b.size();i++)
    {
        ante=i-a.size();

        k2=k2-p1*(b[ante]-'A'+1);

        k2=((k2%M1+M1)%M1)*B1+(b[i]-'A'+1);

        if(k1==k2)
        {
            n++;
            if(n<1000) poz[n]=ante+1;
        }
    }
    fout<<n<<"\n";
    for(i=1;i<=min(1000,n);i++) fout<<poz[i]<<" ";
}