Cod sursa(job #1232966)

Utilizator florinpocolPocol Florin florinpocol Data 24 septembrie 2014 13:19:35
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char a[2000001],b[2000001];
int n,m,cont,solutie[2000001];

int hash(char aux[],int l,int i)
{

    if (i==l)
            return(0);
        else
              return(aux[i]-64+hash(aux,l,i+1));


}


bool verifica(int k)
{
    bool ok;  int i;

    i=k;  ok=true;
    while(i<=k+n-1 && ok==true)
    {
        if (a[i-k]!=b[i])
           ok=false;
           else
           i=i+1;
    }
    return(ok);

}

void RabinKarp(char s[], char sub[]) //se trimit sirurile de lungime n
               //n e lungimea lui sub si m e lungimea lui s
{
    int hs,hsub,i;

    ofstream g("strmatch.out");
    cont=0;
    hs=hash(s,n,0);
    hsub=hash(sub,n,0);
    //cout<<hs<<" "<<hsub;

      for (i=1; i<=m-n+1; i++)
          {
              if (hs == hsub)
                    if (verifica(i)==true)
                           {
                               solutie[cont]=i;
                               cont=cont+1;
                           }

               hs=hs-s[i]+s[n+i+1];
          }

   g<<cont<<"\n";
   for (i=0; i<=cont-1; i++)
       g<<solutie[i]<<" ";

   g.close();
}


void citire()
{
    ifstream f("strmatch.in");
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);

    f.close();
}

int main()
{

    citire();
    RabinKarp(b,a);
    return(0);
}