Cod sursa(job #1752543)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 4 septembrie 2016 13:34:02
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>

using namespace std;
long long n,m,i,k,v1,v2,p1,p2,w1,w2,q[2000005];
char a[2000005],b[2000005];
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a;
    f>>b;
    n=0;
    while(a[n]) n++;
    m=0;
    while(b[m]) m++;
    p1=1;
    p2=1;
    for(i=0; i<n; i++)
    {
        v1=(v1*58+(a[i]-'A'))%1000117;
        v2=(v2*58+(a[i]-'A'))%100109;
        p1=(p1*58)%1000117;
        p2=(p2*58)%100109;
    }
    for(i=0; i<n; i++)
    {
        w1=(w1*58+(b[i]-'A'))%1000117;
        w2=(w2*58+(b[i]-'A'))%100109;
    }
    if(v1==w1&&v2==w2)
    {
        k++;
        q[k]=0;
    }
    for(i=n; i<m; i++)
    {
        w1=(w1*58-p1*(b[i-n]-'A')+(b[i]-'A')+1000234013689)%1000117;
        w2=(w2*58-p2*(b[i-n]-'A')+(b[i]-'A')+10021811881)%100109;
        if(v1==w1&&v2==w2)
        {
            k++;
            q[k]=i+1-n;
        }
    }
    g<<k<<'\n';
    for(i=1; i<=k; i++)
    {
        g<<q[i]<<" ";
    }
    g<<'\n';
    f.close(); g.close();
    return 0;
}