Cod sursa(job #2346938)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 18 februarie 2019 11:36:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 2000005;
const int MOD1 = 666013;
const int MOD2 = 1300727;

int n,m;
char A[NMAX];
char B[NMAX];
int rasp[NMAX];

int main()
{
    fin >> (A+1);
    fin >> (B+1);
    n=strlen(A+1);
    m=strlen(B+1);
    int put1=1,put2=1,baza=71,nr11=0,nr12=0,nr21=0,nr22=0,putere1,putere2;
    for(int i=n;i>=1;i--)
    {
        if(i==1) putere1=put1,putere2=put2;
        nr11+=((A[i]-53)*put1)%MOD1;
        nr11%=MOD1;
        nr12+=((A[i]-53)*put2)%MOD2;
        nr12%=MOD2;
        put1*=baza;
        put2*=baza;
        put1%=MOD1;
        put2%=MOD2;
    }
    put1=1,put2=1;
    for(int i=n;i>=1;i--)
    {
        nr21+=((B[i]-53)*put1)%MOD1;
        nr21%=MOD1;
        nr22+=((B[i]-53)*put2)%MOD2;
        nr22%=MOD2;
        put1*=baza;
        put2*=baza;
        put1%=MOD1;
        put2%=MOD2;
    }
    int k=0;
    if(nr11==nr21 && nr12==nr22)
    {
        rasp[++k]=0;
    }
    for(int i=n+1;i<=m;i++)
    {
        nr21-=((B[i-n]-53)*putere1)%MOD1;
        nr22-=((B[i-n]-53)*putere2)%MOD2;
        if(nr21<0) nr21+=MOD1;
        if(nr22<0) nr22+=MOD2;
        nr21*=baza;
        nr22*=baza;
        nr21+=(B[i]-53);
        nr22+=(B[i]-53);
        nr21%=MOD1;
        nr22%=MOD2;
        if(nr21==nr11 && nr22==nr12)
        {
            rasp[++k]=i-n;
        }
    }
    fout << k << '\n';
    if(k>1000) k=1000;
    for(int i=1;i<=k;i++) fout << rasp[i] << ' ';
    return 0;
}