Cod sursa(job #3353880)

Utilizator Tudor_Iatagan2Iatagan Tudor Tudor_Iatagan2 Data 12 mai 2026 12:28:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <cstring>
using namespace std;
char s1[2000001], s2[2000001], v[2000001];
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main(){
    int l1, l2, p1=1, p2=1, nrs1=0, nrs2=0, i;
    const int b=63, N1=100007, N2=100021;   ///baza 63, N1 si N2 sunt numerele prime mari
    cin>>s1>>s2;
    l1=strlen(s1);
    l2=strlen(s2);
    for( i = 0; i < l1; i++ ){  ///calculam resturile la imp cu N1 resp. N2 ale secventei pe care o cautam
        nrs1=(nrs1*b+s1[i])%N1;
        nrs2=(nrs2*b+s1[i])%N2;
        if( i != 0 ){   ///crestem puterea doar daca nu suntem pe primul element
            p1=(p1*b)%N1;
            p2=(p2*b)%N2;
        }
    }
    if( l1 > l2 ) //daca lungimea lui s1 e mai mare decat s2, atunci nu poate aparea in s2
        cout<<0;
    else{
        int nr1=0, nr2=0;
        for( i = 0; i < l1; i++ ){  ///calculam resturile la imp cu N1 resp. N2 ale primei secvente din s2
            nr1=(nr1*b+s2[i])%N1;
            nr2=(nr2*b+s2[i])%N2;
        }
        int k=0;
        if( nr1 == nrs1 && nr2 == nrs2 )    ///verificam prima secventa
            v[k++]=1;
        for( i = l1; i < l2; i++ ){ ///verificam toate celelalte secvente
            ///scot s2[i-l1] si adaug s2[i]
            nr1=((nr1-(s2[i-l1]*p1)%N1+N1)*b+s2[i])%N1;
            nr2=((nr2-(s2[i-l1]*p2)%N2+N2)*b+s2[i])%N2;
            if( nr1 == nrs1 && nr2 == nrs2 ){   ///daca secventa e buna
                v[i-l1+1]=1;
                k++;
            }
        }
        cout<<k<<'\n';
        k=0;
        for( i = 0; i < l2 && k < 1000; i++ )   ///afisez primele 1000 de pozitii ale secventelor bune
            if( v[i] == 1 ){
                k++;
                cout<<i<<' ';
            }
    }
    return 0;
}