Cod sursa(job #1229180)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 16 septembrie 2014 18:13:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <string.h>
#define modf 100007
#define mods 100021
#define NMax 2000001
#define bs 73
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>>a>>b;
    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\n";
        return 0;
    }
    for (i=strlen(a); 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";
    for (i=1; i<=n && i<=1000; i++)
        g<<poz[i]<<" ";
    return 0;
}