Cod sursa(job #854470)

Utilizator RamaStanciu Mara Rama Data 13 ianuarie 2013 17:21:56
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<fstream>
#include<string>
#include<vector>
#define mod1 666001
#define mod2 666013

using namespace std;

string A,B;
vector <int> I;
int cod1,cod2,h1,h2,k2;


int litere(char c)
{
    int x=0;
    if (c>='A' && c<='Z') x=c-'A';
        else if (c>='a' && c<='z') x=c-'a'+26;
            else x=c-'0' +52;
    return x;
}

void solveA()
{

    int c1=0,c2=0;
    int length=A.size();
    for (int i=0;i<length;i++)
    {

        c1=((c1*62)%mod1+litere(A[i]))%mod1;
        c2=((c2*62)%mod2+litere(A[i]))%mod2;
    }
    cod1=c1;
    cod2=c2;
}


void solveB()
{
    int k1,pow1=1,pow2=1;
    int length=A.size();
    for (int i=0;i<length;i++)
    {
        h1=((h1*62)%mod1+litere(B[i]))%mod1;
        h2=((h2*62)%mod2+litere(B[i]))%mod2;
        if (i>0)
        {
            pow1=(pow1*62)%mod1;
            pow2=(pow2*62)%mod2;
        }
    }
    k1=0;
    if (h1==cod1 && h2==cod2)
    {
        k2++;
        I.push_back(0);
    }
    int length2=B.size();
    for (int i=length;i<length2;i++)
    {
        h1=(h1-(pow1*litere(B[k1]))%mod1+mod1)%mod1;
        h2=(h2-(pow2*litere(B[k1]))%mod2+mod2)%mod2;

        h1=((h1*62)%mod1+litere(B[i]))%mod1;
        h2=((h2*62)%mod2+litere(B[i]))%mod2;

        k1++;
        if (h1==cod1 && h2==cod2)
        {
            k2++;
            if (k2<=1000)
            I.push_back(k1);
        }
    }
}

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in>>A;
    in>>B;
    solveA();
    solveB();
    out<<k2<<"\n";
    for (int i=0;i<I.size();i++)
    {
        out<<I[i]<<" ";
    }
    return 0;
}