Cod sursa(job #2470782)

Utilizator adiaioanaAdia R. adiaioana Data 9 octombrie 2019 18:54:14
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <cmath>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long l1, l2, r[3],rm[3], rc[3],P;
int sol, v[1100];
char sir1[2000100], sir2[2000100];

int ind(char ch);
void scan();
void print();
int main()
{
    scan();
    if(l1>l2)
    {
        cout<<0<<'\n';
        return 0;
    }

    rm[1]=rm[2]=1; rc[1]=rc[2]=0;
    for(int i=0; i<l1; ++i)
    {
        rc[1]=(rc[1]*73+ind(sir1[i]))%MOD1;
        rc[2]=(rc[2]*73+ind(sir1[i]))%MOD2;
        if(i)
        {
            rm[2]=(rm[2]*73)%MOD2;
            rm[1]=(rm[1]*73)%MOD1;
        }
    }
    r[1]=r[2]=0;
    for(int i=0; i<l1; ++i)
    {
        r[1]=(r[1]*73+ind(sir2[i]))%MOD1;
        r[2]=(r[2]*73+ind(sir2[i]))%MOD2;
    }

    if(r[1]==rc[1] && r[2]==rc[2])
        v[++sol]=0;
    for(int i=l1; i<l2 && sol<1000; ++i)
    {
        r[1]=(r[1]+MOD1-(rm[1]*ind(sir2[i-l1]))%MOD1)*73 +ind(sir2[i]);
        r[2]=(r[2]+MOD2-(rm[2]*ind(sir2[i-l1]))%MOD2)*73 +ind(sir2[i]);
        r[2]%=MOD2; r[1]%=MOD1;

        if(r[1]==rc[1] && r[2]==rc[2])
            v[++sol]=i-l1+1;
    }

    print();

    return 0;
}

void scan()
{
    cin>>sir1;
    cin.get();
    cin>>sir2;
    l1=strlen(sir1);
    l2=strlen(sir2);
}

int ind(char ch)
{
    if(ch>='a' && ch<='z')
        return 27+ch-'a';
    else return ch-'A'+1;
}

void print()
{
    cout<<sol<<'\n';
    for(int i=1; i<=min(sol,1000); ++i)
        cout<<v[i]<<' ';
    cout<<'\n';
}