Cod sursa(job #2085016)

Utilizator naomitrancaNaomi Tranca naomitranca Data 9 decembrie 2017 15:47:33
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <string.h>
using namespace std;
int cod (char c)
/// returneaza codul unui caracter
/// a-0...z-25, A-26...Z-51, 0-52...9-61
{
    if (c>='a' && c<='z')
        return c-'a';
    if (c>='A' && c<='Z')
        return (c-'A')+26;
    return c-'0'+52;
}

long long prim=10000000003;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char P[2000002],T[2000002];
int lp,lt;
int nrap,k,i,t;
long long vp,vt,val;
int main()
{
    fi.getline(P,2000002);
    fi.getline(T,2000002);
    lp=strlen(P);
    lt=strlen(T);
    vp=0;
    for (int i=0;i<lp;i++)
        vp=(vp*26+cod(P[i])) % prim;
    vt=0;
    for (int i=0;i<lp;i++)
        vt=(vt*26+cod(T[i])) % prim;
    if (vt==vp)
        nrap=1;
    else
        nrap=0;
    val=1;
    for (int i=1;i<=lp-1;i++)
        val=(val*26)%prim;
    for (int k=1;k<lt-lp+1;k++)
    {
        vt=vt-cod(T[k-1])*val;
        vt=(vt*26+cod(T[k-1+lp]))%prim;
        if (vt==vp)
            nrap++;
    }
    fo<<nrap<<"\n";
    vt=0;
    for (int i=0;i<lp;i++)
        vt=(vt*26+cod(T[i])) % prim;
    if (vt==vp)
        fo<<0<<" ";
    val=1;
    for (int i=1;i<=lp-1;i++)
        val=(val*26)%prim;
    for (int k=1;k<lt-lp+1;k++)
    {
        vt=vt-cod(T[k-1])*val;
        vt=(vt*26+cod(T[k-1+lp]))%prim;
        if (vt==vp)
            fo<<k<<" ";
    }
    fi.close();
    fo.close();
    return 0;
}