Cod sursa(job #854467)

Utilizator RamaStanciu Mara Rama Data 13 ianuarie 2013 17:19:12
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 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,k1=0;


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 &cod1,int &cod2)
{
    int c1=0,c2=0;
    int s=A.size()-1;
    for (int i=0;i<=s;i++)
    {

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

}
void solveB()
{
    int i,length=A.size()-1,k2=0;
    int pow1=1,pow2=1;

    for(i=0;i<=length;i++)
    {
        h1=((h1*62)%mod1+litere(B[i]))%mod1;
        h2=((h1*62)%mod2+litere(B[i]))%mod2;
        if (i) {pow1=(pow1*62)%mod1; pow2=(pow2*62)%mod2; }
    }

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

    int length2=B.size();

        for(i=length+1;i<length2;i++)
        {

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

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

}
int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in>>A;
    in>>B;
    out<<A<<"\n";

    out<<B<<"\n";
    solveA(cod1,cod2);
    solveB();

   // printf("%d\n ",k1);

    //for(int j=0;j<k1;j++)
       // {printf("%d ",I[j]);}

    out<<k1<<"\n";
    for (int i=0;i<I.size();i++)
    {
        out<<I[i]<<" ";
    }
    return 0;
}