Cod sursa(job #1838148)

Utilizator vancea.catalincatalin vancea.catalin Data 31 decembrie 2016 01:56:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<iostream>
#include<fstream>
#include<string>
#define B 67
#define M1 28000000
#define M2 28000011
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
int p1=1,p2=1,k1,k2,k3,k4,aux;
int poz[1111];
int to(char c)
{
    if('0'<=c&&c<='9') return (c-'0');
    if('A'<=c&&c<='Z') return (c-'A')+10;
    if('a'<=c&&c<='z') return (c-'a')+36;
}
int main()
{
    int i,ante,j,n=0;
    fin>>a>>b;
    for(i=0;i<a.size();i++)
    {
        if(i>0) p1=(p1*B)%M1;
        if(i>0) p2=(p2*B)%M2;
        k1=(k1*B+to(a[i]))%M1;
        k2=(k2*B+to(a[i]))%M2;
    }
    for(i=0;i<a.size();i++)
    {
        k3=(k3*B+to(b[i]))%M1;
        k4=(k4*B+to(b[i]))%M2;
    }
    if(k1==k3 && k2==k4)
    {
        n++;
        poz[n]=0;
    }
    aux=k3;
    for(i=a.size();i<b.size();i++)
    {
        ante=i-a.size();
        aux=(k3-p1*to(b[ante]))%M1;
        k3=(k3-p1*to(b[ante]))%M1;
        k4=(k4-p2*to(b[ante]))%M2;

        k3=(((k3+M1)%M1)*B+to(b[i]))%M1;
        k4=(((k4+M2)%M2)*B+to(b[i]))%M2;

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