Cod sursa(job #1514303)

Utilizator mirunazMiruna Zavelca mirunaz Data 30 octombrie 2015 23:00:04
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include<cstdio>
#include<cstring>
# define MOD 666013
using namespace std;
int i,j,n,k,m=0,x,y,c=0,s=0,v[1001];
char s1[2000001],s2[2000001];
FILE *in,*out;
int main ()
{
    in=fopen("strmatch.in","r");
    out=fopen("strmatch.out","w");
    fscanf(in,"%s %s",&s2,&s1);
    n=strlen(s1);
    k=strlen(s2);
    for(i=0;i<k;i++)
    {
        //numarul caracteristic sirului de cautat
        if(s2[i]>='A' && s2[i]<='Z')
            x=s2[i]-'A';
        else if(s2[i]>='a' && s2[i]<='z')
            x=26+s2[i]-'a';
        else
            x=52+s2[i]-'0';
        c*=62;
        c%=MOD;
        c+=x;
        //numarul caracteristic primului subsir de lungime k din sirul in care caut
        if(s1[i]>='A' && s1[i]<='Z')
            x=s1[i]-'A';
        else if(s1[i]>='a' && s1[i]<='z')
            x=26+s1[i]-'a';
        else
            x=52+s1[i]-'0';
        s*=62;
        s%=MOD;
        s+=x;
    }
    if(s==c)
    {
        int pp=1;
        for(j=0;j<k && pp==1;j++)
            if(s2[j]!=s1[i-k+j])
                pp=0;
        if(pp==1)
        {
            m++;
            v[m]=i-k;
        }
    }
    for(i=k;i<n && m<1000;i++)
    {
        if(s1[i]>='A' && s1[i]<='Z')
            x=s1[i]-'A';
        else if(s1[i]>='a' && s1[i]<='z')
            x=26+s1[i]-'a';
        else
            x=52+s1[i]-'0';
        //elimin ultimul caracter de ordin prea mic pentru numarul nou creat
        if(s1[i-k]>='A' && s1[i-k]<='Z')
            y=s1[i-k]-'A';
        else if(s1[i-k]>='a' && s1[i-k]<='z')
            y=26+s1[i-k]-'a';
        else
            y=52+s1[i-k]-'0';
        for(j=1;j<k;j++)
        {
            y*=62;
            y%=MOD;
        }
        s-=y;
        s*=62;
        s%=MOD;
        s+=x;
        /*if(s==c)
        {
            int pp=1;
            for(j=0;j<k && pp==1;j++)
                if(s2[j]!=s1[i-k+j+1])
                    pp=0;
            if(pp==1)
            {
                m++;
                v[m]=i-k+1;
            }
        }*/
    }
    fprintf(out,"%d\n",m);
    for(i=1;i<=m;i++)
        fprintf(out,"%d ",v[i]);
    return 0;
}