Cod sursa(job #2208982)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 1 iunie 2018 14:12:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int baza=62;
const int p1=666019,p2=666013;
char a[2000003],b[2000003];
int poz[2000003];
int  put1=1,rp1=0,n,m,cnt=0,rp2=0,put2=1;
void citire ()
{
    in.getline(a,2000000);
    in>>ws;
    in.getline(b,2000000);
    m=strlen(a);
    n=strlen(b);
    for(int i=0;i<m;++i)
    {
        if(a[i]>='0' && a[i]<='9')
            a[i]=a[i]-'0';
        if(a[i]>='a' && a[i]<='z')
            a[i]=a[i]-'a'+10;
        if(a[i]>='A' && a[i]<='Z')
            a[i]=a[i]-'A'+36;
    }
    for(int i=0;i<n;++i)
    {
        if(b[i]>='0' && b[i]<='9')
            b[i]=b[i]-'0';
        if(b[i]>='a' && b[i]<='z')
            b[i]=b[i]-'a'+10;
        if(b[i]>='A' && b[i]<='Z')
            b[i]=b[i]-'A'+36;
    }
}
void frmput ()
{
    for(int i=0;i<m;++i)
        put1=(put1*baza)%p1;
    for(int i=0;i<m;++i)
        put2=(put2*baza)%p2;
}
void frmrp ()
{
    for(int i=0;i<m;++i)
    {
        rp1=(rp1*baza)%p1;
        rp1=(rp1+a[i])%p1;
    }
    for(int i=0;i<m;++i)
    {
        rp2=(rp2*baza)%p2;
        rp2=(rp2+a[i])%p2;
    }
}
void rez ()
{
    int i,rc1=0,rc2=0;
    for(i=0;i<n;++i)
    {
        rc1=(rc1*baza)%p1;
        rc1=(rc1+b[i])%p1;
        rc2=(rc2*baza)%p2;
        rc2=(rc2+b[i])%p2;
        if(i>=m)
        {
            rc1=(rc1+p1-(put1*b[i-m])%p1)%p1;
            rc2=(rc2+p2-(put2*b[i-m])%p2)%p2;
            if(rc1==rp1 && rc2==rp2)
                poz[++cnt]=i-m+1;
        }
        if(rc1==rp1 && i==m-1 && rc2==rp2)
            poz[++cnt]=i-m+1;
    }
}
int main()
{
    citire();
    frmput();
    frmrp();
    rez();
    out<<cnt<<'\n';
    if(cnt>=1000)
        cnt=1000;
    for(int i=1;i<=cnt;++i)
        out<<poz[i]<<' ';
    return 0;
}