Cod sursa(job #2772633)

Utilizator Leonard123Mirt Leonard Leonard123 Data 1 septembrie 2021 22:23:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define NMAX 20000000
char A[NMAX],B[NMAX];
int NA, NB, hashA=0, hashB=0,P=33, PA=1, SOL[NMAX], k=0;
 
int main()
{
    cin>>A;
    cin>>B;
    NA=strlen(A);
    NB=strlen(B);
    if(NA>NB){
        cout<<0;
        return 0;
    }
    for(int i=0;i<NA;i++){
        hashA= hashA*P + A[i];
        if(i!=0)
            PA=PA*P;
    }
    for(int i=0;i<NA;i++){
        hashB= hashB*P + B[i];
    }
    if(hashA==hashB)
        SOL[++k]=0;
    for(int i=NA;i<NB;i++){
        hashB= (hashB-(B[i-NA]*PA))*P + B[i];
        if(hashA==hashB)
            SOL[++k]=i-NA+1;
    }
    cout<<k<<endl;
    for(int i=1;i<=k&&i<=1000;i++)
        cout<<SOL[i]<<' ';
}