Cod sursa(job #2545280)

Utilizator evelina.nitoiuNitoiu Evelina evelina.nitoiu Data 12 februarie 2020 22:54:01
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define N1 100007
#define N2 100021

using namespace std;

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

char s1[2000001], s2[2000001];
int Ns1, Ns2;
int nrs1, nrs2, p1, p2;
char v[2000001];

int main(){
    in>>s1>>s2;
    Ns1=strlen(s1);
    Ns2=strlen(s2);
    p1=p2=1;
    nrs1=nrs2=0;
    for (int i=0;i<Ns1;i++){
        nrs1=(nrs1*73+s1[i])% N1;
        nrs2=(nrs2*73+s1[i])% N2;
        if (i!=0)
            p1=(p1*73)% N1,
            p2=(p2*73)%N2;
    }
    if (Ns1>Ns2){
        printf("0\n");
    }
    else{
        int nr1=0,nr2=0;
        for (int i=0;i<Ns1;i++){
            nr1=(nr1*73+s2[i])%N1;
            nr2=(nr2*73+s2[i])%N2;
        }
        int k=0;
        if (nr1==nrs1&&nr2==nrs2){
            v[0]=1;
            k++;
        }
        for (int i=Ns1;i<Ns2;i++){
            nr1=((nr1-(s2[i-Ns1]*p1)%N1+N1)*73+s2[i])%N1;
            nr2=((nr2-(s2[i-Ns1]*p2)%N2+N2)*73+s2[i])%N2;
            if (nr1==nrs1&&nr2==nrs2){
                v[i-Ns1+1]=1;
                k++;
            }
        }
        out<<k<<"\n";
        k = 0;
        for (int i=0;i<Ns2&&k<1000;i++)
            if(v[i]==1){
                k++;
                out<<i<<" ";
            }
        out<<"\n";
    }
    return 0;
}