Cod sursa(job #1229223)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 16 septembrie 2014 19:08:48
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <string.h>
#define modf 100007
#define mods 100021
#define NMax 2000001
#define bse 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int hashf, hashs, p1, p2, foundf, foundss, poz[NMax], i, n;
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*bse+a[i])%modf;
        hashs=(hashs*bse+a[i])%mods;
        if (i!=0) {
            p1=(p1*bse)%modf;
            p2=(p2*bse)%mods;
        }
    }
    if (strlen(a) > strlen(b)) {
        g<<"0\n";
        return 0;
    }
    for (i=0; i<strlen(a); i++) {
        foundf=(foundf*bse+a[i])%modf;
        foundss=(foundss*bse+a[i])%mods;
    }
    if (foundf==hashf && foundss==hashs) {
        poz[0]=1;
        n++;
    }
    for (i=strlen(a); i<strlen(b); i++) {
        foundf=((foundf-(p1*b[i-strlen(a)])%modf+modf)*bse+b[i])%modf;
        foundss=((foundss-(p2*b[i-strlen(a)])%mods+mods)*bse+b[i])%mods;
        if (foundf==hashf && foundss==hashs) {
            poz[i-strlen(a)+1]=1;
            n++;
        }
    }
    g<<n<<"\n";
    n=0;
    for (i=0; i<strlen(b) && n<1000; i++)
        if (poz[i]==1) {
            g<<i<<" ";
            n++;
        }
    g<<"\n";
    return 0;
}