Cod sursa(job #1229162)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 16 septembrie 2014 17:43:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string.h>
#define modf 100007
#define mods 666013
#define NMax 2000001
#define bs 71
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int hashf, hashs, p1, p2, foundf, founds, n, poz[1001], i;
char a[NMax], b[NMax];
int main()
{
    f.get(a, 2000001);
    f.get();
    f.get(b, 2000001);
    p1=1;
    p2=1;
    for (i=0; i<strlen(a); i++) {
        hashf=(hashf*bs+a[i])%modf;
        hashs=(hashs*bs+a[i])%mods;
        if (i==0)
            continue;
        p1=(p1*bs)%modf;
        p2=(p2*bs)%mods;
    }
    if (strlen(a) > strlen(b)) {
        g<<"0";
        return 0;
    }
    for (i=0; i<strlen(b); i++) {
        foundf=((foundf-(p1*b[i-strlen(a)])%modf+modf)*bs+b[i])%modf;
        founds=((founds-(p2*b[i-strlen(a)])%mods+mods)*bs+b[i])%mods;
        if (foundf==hashf && founds==hashs)
            poz[++n]=i-strlen(a)+1;
    }
    g<<n<<"\n";
    if (n>1000)
        n=1000;
    for (i=1; i<=n; i++)
        g<<poz[i]<<" ";
    return 0;
}