Cod sursa(job #2058796)

Utilizator vancea.catalincatalin vancea.catalin Data 6 noiembrie 2017 10:13:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#define B1 69
#define B2 97
#define M1 11243567
#define M2 19898746
using namespace std;
fstream fin("strmatch.in",ios::in),fout("strmatch.out",ios::out);
string a,b;
vector<int> v;
int r,r1,r2,r3,r4,p1,p2;
int to_int(char c)
{
    if('0'<=c && c<='9') return (c-'0')+1;
    if('A'<=c && c<='Z') return (c-'A')+11;
    if('a'<=c && c<='z') return (c-'a')+36;
    //am 10+25+25 caractere si inca 1 sa scap de 0 (61)
}
int main()
{
    int i,j,ind;
    fin>>a>>b;
    p1=p2=1;
    for(i=0;i<a.size();i++)
    {
        if(i>0) p1=(p1*B1)%M1;
        if(i>0) p2=(p2*B2)%M2;

        r1=(r1*B1+to_int(a[i]))%M1;
        r2=(r2*B2+to_int(a[i]))%M2;
    }
    for(i=0;i<a.size()-1;i++)
    {
        r3=((r3*B1)+to_int(b[i]))%M1;
        r4=((r4*B2)+to_int(b[i]))%M2;
    }
    for(i=a.size()-1;i<b.size();i++)
    {
        ind=i-a.size()+1;
        r3=((r3*B1)+to_int(b[i]))%M1;
        r4=((r4*B2)+to_int(b[i]))%M2;

        if(r3==r1 && r4==r2)
        {
            r++;
            v.push_back(ind);
        }

        r3=(((r3-p1*to_int(b[ind]))%M1)+M1)%M1;
        r4=(((r4-p2*to_int(b[ind]))%M2)+M2)%M2;
    }

    fout<<r<<"\n";
    if(r>1000) r=1000;
    for(i=0;i<r;i++)
    {
        fout<<v[i]<<" ";
    }
}