Cod sursa(job #2976418)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 9 februarie 2023 09:45:00
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <cstring>
#define MOD 1000007
#define B 26
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int i, j, n, m, n1, n2, hash1, hash2, pow, k;
char a[2000002], b[2000002];
int sol[2000002];
int main() {
    cin>>a>>b;
    n1=strlen(a);
    n2=strlen(b);
    if(n1>n2){
        cout<<"0";
        return 0;
    }
    pow=1;
    for(i=0;i<n1;i++){
        hash1=(hash1*B+a[i])%MOD;
        if(i>0){
            pow=pow*B;
            pow=pow%MOD;
        }
    }
    for(i=0;i<n1;i++){
        hash2=(hash2*B+b[i])%MOD;
    }
    if(hash1==hash2)
        sol[++k]=0;
    for(i=n1;i<n2;i++){
        hash2=hash2-pow*b[i-n1];
        if(hash2<0)
            hash2+=MOD;
        hash2=(hash2*B+b[i])%MOD;
        if(hash2==hash1){
            sol[++k]=i-n1+1;
        }
    }
    cout<<k<<"\n";
    for(i=1;i<=min(k, 1000);i++)
        cout<<sol[i]<<" ";


}