Cod sursa(job #1173503)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 19 aprilie 2014 20:45:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
//RABIN KARP
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int NA,NB,pattern,text,pat,lg,sol[2000005];
const int baza=73;
const int prim=666013;
char A[2000005],B[2000005];

inline void Citire()
{
    fin>>(A+1)>>(B+1);
}

inline bool Verifica(int poz)
{
    int i,ca;
    ca=NA;
    for (i=poz;i>=poz-NA+1;i--)
        {
            if (B[i]!=A[ca])
                return 0;
            ca--;
        }
    return 1;
}

inline void Init()
{
    int i,putere=1;
    for (i=NA;i>=1;i--)
        {
            if (i==1)
                pat=putere;
            pattern+=((int)A[i]*putere)%prim;
            pattern%=prim;
            putere*=baza;
            putere%=prim;
        }
    putere=1;
    for (i=NA;i>=1;i--)
        {
            text+=((int)B[i]*putere)%prim;
            text%=prim;
            putere*=baza;
            putere%=prim;
        }
    if (text==pattern)
        if (Verifica(NA))
            sol[++lg]=0;
}

inline void Rezolva()
{
    int i;
    NA=strlen(A+1);
    NB=strlen(B+1);
    Init();
    for (i=NA+1;i<=NB;i++)
        {
            text=text-((int)B[i-NA]*pat)%prim;
            if (text<0) text+=prim;
            text=text*baza;
            text+=(int)B[i];
            text%=prim;
            if (text==pattern)
                if (Verifica(i))
                    sol[++lg]=i-NA;
        }
}

int main()
{
    Citire();
    Rezolva();
    fout<<lg<<"\n";
    if (lg>1000)
        lg=1000;
    for (int i=1;i<=lg;i++)
        fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}