Cod sursa(job #1301649)

Utilizator RaileanuCristian Raileanu Raileanu Data 26 decembrie 2014 11:48:01
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream f1("strmatch.in");
ofstream f2("strmatch.out");
#define MX 2000010
#define B 2
const int prime= 0x10001 ;
int i,n,m, c[MX], nc ; // c - coada solutiilor
char a[MX],b[MX];

unsigned int f_hash(char s[], int st, int dr )
{
    unsigned int v=0;
    for (i=st; i<=dr; i++ )
        {v+= (1<<(dr-i) ) *s[i] ;
         v%=prime; }
    return v;
}

bool verifica(char s1[], int n, char s2[], int st )
{
    for (int i=0; i<=n; i++)
        if (s1[i] != s2[st+i] ) return 0;
    return 1;
}

void cauta_ap(char s1[], int n, char s2[], int m )
{
    unsigned int v1= f_hash(s1,0,n), v=f_hash(s2,0,n), p=1<<n , i;

    for (i=n ; i<=m; i++ )
        {
            if (v==v1 )
                if (verifica(s1,n,s2,i-n ) )
                    c[++nc]=i-n;
            v= (v- s2[i-n]*p)*2 + s2[i+1];
            v%=prime ;
        }
}

void test()
{
    cout<<f_hash(a,0,1)<<"\n";
    cout<<f_hash(b,1,2)<<"\n";
    cout<<verifica(a,n-2,b,2);
}

int main()
{
    f1>>a;
    f1>>b;
    n=strlen(a);
    m=strlen(b);

    if (n>m) {f2<<0; return 0; } // cazul imposibilitatii

    cauta_ap(a,n-1,b,m-1);

    f2<<nc<<"\n";
    for (i=1; i<=nc; i++)
            f2<<c[i]<<" ";
    f2.close();
    return 0;
}