Cod sursa(job #2207690)

Utilizator MocanuAlAlexandru Mocanu MocanuAl Data 26 mai 2018 13:46:49
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <fstream>
#include <string.h>

using namespace std;

int v[1001];
char a[2000001],b[2000001];
int main()
{
    ifstream cin ("strmatch.in");
    ofstream cout ("strmatch.out");
    int inr2,r1,r2,r1ct,r2ct,cput,putere,m,n,i,mod1=666013,mod2=666019,nr=0,poz=0,nrd=0,inr,sol=0;
    cin>>a;
    n=strlen(a);
    cin>>b;
    m=strlen(b);
    i=0;
    putere=n-1;
    while(i<n)
    {
        cput=putere;
        nrd=1;
        while(cput>0)
        {
            nrd=nrd*62;
            cput--;
        }
        if(a[i]>='0' && a[i]<='9')
            inr=a[i]-48;
        else if(a[i]>='A' && a[i]<='Z')
            inr=a[i]-65+10;
        else
            inr=a[i]-97+36;
        nr=nr+nrd*inr;
        i++;
        putere--;
    }
    r1ct=nr%mod1;
    r2ct=nr%mod2;
    while(poz+n<=m)
    {
        i=poz;
        putere=n-1;
        if(poz==0)
        {
            nr=0;
            while(i<=poz+n-1)
            {
                cput=putere;
                nrd=1;
                while(cput>0)
                {
                    nrd=nrd*62;
                    cput--;
                }
                if(b[i]>='0' && b[i]<='9')
                    inr=b[i]-48;
                else if(b[i]>='A' && b[i]<='Z')
                    inr=b[i]-65+10;
                else
                    inr=b[i]-97+36;
                nr=nr+nrd*inr;
                i++;
                putere--;
            }
        }
        else
        {
            nrd=1;
            cput=putere;
            while(cput>0)
            {
                nrd=nrd*62;
                cput--;
            }
            if(b[poz-1]>='0' && b[poz-1]<='9')
                    inr=b[poz-1]-48;
                else if(b[poz-1]>='A' && b[poz-1]<='Z')
                    inr=b[poz-1]-65+10;
                else
                    inr=b[poz-1]-97+36;
            if(b[poz+n-1]>='0' && b[poz+n-1]<='9')
                    inr2=b[poz+n-1]-48;
                else if(b[poz+n-1]>='A' && b[poz+n-1]<='Z')
                    inr2=b[poz+n-1]-65+10;
                else
                    inr2=b[poz+n-1]-97+36;
            nr=(nr-inr*nrd)*62+inr2;
        }
        r1=nr%mod1;
        r2=nr%mod2;
        if(r1ct==r1 && r2ct==r2)
        {
            sol++;
            if(sol<=1000)
                v[sol]=poz;
        }
        poz++;
    }
    cout<<sol<<endl;
    if(sol<=1000)
        for(i=1; i<=sol; i++)
            cout<<v[i]<<" ";
    else
        for(i=1; i<=1000; i++)
            cout<<v[i]<<" ";
    return 0;
}