Cod sursa(job #2085044)

Utilizator naomitrancaNaomi Tranca naomitranca Data 9 decembrie 2017 16:42:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <stdio.h>
#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;
}

int prim=71;

FILE *fi,*fo;
int PUTERI[2000002];
int X[2000002];
int S[2000002];
char P[2000002],T[2000002];
int lp,lt;
int nrap,st,dr;
int vp,vt,val;
int factor;

int main()
{
    fi=fopen("strmatch.in","r");
    fo=fopen("strmatch.out","w");
    fscanf(fi,"%s",P+1);
    fscanf(fi,"%s",T+1);
    lp=strlen(P+1);
    lt=strlen(T+1);
    PUTERI[0]=PUTERI[1]=1;
    for (int i=2;i<=lt;i++)
        PUTERI[i]=PUTERI[i-1]*prim;
    for (int i=1;i<=lt;i++)
        X[i]=PUTERI[i]*cod(T[i]);
    S[0]=0;
    for (int i=1;i<=lt;i++)
        S[i]=S[i-1]+X[i];
    vp=0;
    factor=1;
    for (int i=1;i<=lp;i++)
    {
        vp=vp+cod(P[i])*factor;
        factor=factor*prim;
    }
    vp=vp*PUTERI[lt];
    nrap=0;
    for (dr=lp;dr<=lt;dr++)
    {
        st=dr-lp+1;
        val=S[dr]-S[st-1];
        val=val*PUTERI[lt+1-st];
        if (val==vp)
            nrap++;
    }
    fprintf(fo,"%d\n",nrap);
    for (dr=lp;dr<=lt;dr++)
    {
        st=dr-lp+1;
        val=S[dr]-S[st-1];
        val=val*PUTERI[lt+1-st];
        if (val==vp)
            fprintf(fo,"%d ",st-1);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}