Cod sursa(job #3238482)

Utilizator AllerAller Aller Aller Data 25 iulie 2024 19:21:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int dim=2000001, mod=1e9+7;

int main()
{
    int n, m, i, nr1=0, nr2=0, putere[dim], sol[1001], k=0;
    char a[dim], b[dim];
    f>> a >> b;
    n=strlen(a); m=strlen(b);
    putere[0]=1;
    nr1=(a[0]-'0'); nr2=(b[0]-'0');
    for(i=1; i<n; i++){
        nr1=(nr1*127LL+(a[i]-'0'))%mod;
        nr2=(nr2*127LL+(b[i]-'0'))%mod;
        putere[i]=(putere[i-1]*127LL)%mod;
    }
    putere[n]=(putere[n-1]*127LL)%mod;
    if(nr1==nr2){
        sol[++k]=0;
    }
    for(i=n; i<m; i++){
        nr2=((nr2*127LL+(b[i]-'0'))-(1LL*(b[i-n]-'0')*putere[n]%mod)+mod)%mod;
        if(nr1==nr2){
            k++;
            if(k<=1000){
                sol[k]=i-n+1;
            }
        }
    }
    g<< k << endl;
    k=min(k, 1000);
    for(i=1; i<=k; i++){
        g<< sol[i] << " ";
    }

    return 0;
}