Cod sursa(job #2047077)

Utilizator vladutzu444Ciubotariu Vlad vladutzu444 Data 24 octombrie 2017 15:38:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstring>
#define MAXN 2000001
#define X 73
#define MOD 100007
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char A[MAXN],B[MAXN];
char match[MAXN];
int main()
{   f>>A>>B;
    int NA=strlen(A),NB=strlen(B);
    if(NA>NB) {g<<"0\n"; g.close(); return 0;}
    int P=1,ha=0,hb=0;
    for(int i=0;i<NA;i++)
    {   ha=(ha*X+A[i])%MOD;
        hb=(hb*X+B[i])%MOD;
        if(i)P=P*X%MOD;
    }
    int Nr=0;
    if(hb==ha) {match[0]=1; Nr++;}
    for(int i=NA;i<NB;i++)
    {   hb=((hb-(B[i-NA]*P)%MOD+MOD)%MOD*X+B[i])%MOD;
        if(hb==ha) {match[i-NA+1]=1; Nr++;}
    }
    g<<Nr<<'\n';
    for(int i=0;i<NB && Nr;i++)
        if(match[i]) {Nr--; g<<i<<' ';}
    g<<'\n'; g.close(); return 0;
}