Cod sursa(job #2675054)

Utilizator DarkwarriorRobert Gaspar Darkwarrior Data 21 noiembrie 2020 09:43:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
#define p 73
#define MOD1 100007
#define MOD2 100021
char s1[2000009],s2[2000009];
int p1=1,p2=1;
int ans[1009],k,n,m;
int HASH1,HASH2 ,Hash1,Hash2;
int main(){
    f>>s1>>s2;
    n=strlen(s1);
    m=strlen(s2);
    for(int i=0;i<n;i++){
        HASH1=(HASH1*p+s1[i])%MOD1;
        HASH2=(HASH2*p+s1[i])%MOD2;
        if(i!=0)
            p1=(p1*p)%MOD1,p2=(p2*p)%MOD2;
    }
    for(int i=0;i<n;i++){

        Hash1=(Hash1*p+s2[i])%MOD1;

        Hash2=(Hash2*p+s2[i])%MOD2;
    }
    if(HASH1==Hash1&&HASH2==Hash2)
        ans[++k]=0;
    for(int i=n;i<m;i++){
        Hash1=((Hash1-(s2[i-n]*p1)%MOD1+MOD1)*p+s2[i])%MOD1;
        Hash2=((Hash2-(s2[i-n]*p2)%MOD2+MOD2)*p+s2[i])%MOD2;
        if(HASH1==Hash1&&HASH2==Hash2){
            k++;
            if(k<=1000)
                ans[k]=i-n+1;
        }
    }
        g<<k<<"\n";
    for(int i=1;i<=min(1000,k);i++)
        g<<ans[i]<<' ';
}