Cod sursa(job #2042500)

Utilizator DavidLDavid Lauran DavidL Data 18 octombrie 2017 18:48:05
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000005
#define PRIM 1000000007LL
#define LL long long
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

char A[MAX],B[MAX];
int a,b;
int n;
vector <LL> rez;

int cod(char c)
{
    if ('a'<=c && c<='z')
        return c-'a';
    if ('A'<=c && c<='Z')
        return c-'A'+26;
    if ('0'<=c && c<='9')
        return c-'0'+52;
}

int main()
{
    fi>>A+1>>B+1;
    a=strlen(A+1),b=strlen(B+1);
    if (a>b)
    {
        fo<<0;
        return 0;
    }
    LL v=1; ///62^(a-1)
    for (int i=1; i<a; i++)
    {
        v=(1LL*v*62)%PRIM;
    }
    LL nr=0,vhash=0;
    for (int i=1; i<=a; i++)
    {
        nr=(1LL*nr*62+cod(A[i]))%PRIM;
        vhash=(1LL*vhash*62+cod(B[i]))%PRIM;
    }
    for (int sf=a; sf<=b; sf++)
    {
        if (nr==vhash)
        {
            n++;
            rez.push_back(sf-a);
        }

        vhash=(PRIM+vhash-1LL*v*cod(B[sf-a+1]))%PRIM;
        vhash=(1LL*vhash*62+cod(B[sf+1]))%PRIM;
    }
    fo<<n<<"\n";
    for (int i=0; i<min(n,1000); i++)
        fo<<rez[i]<<" ";
    return 0;
}