Cod sursa(job #1812388)

Utilizator rangalIstrate Sebastian rangal Data 22 noiembrie 2016 00:24:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
/*
    Problema se bazeaza pe aceeasi idee ca Potrivirea Sirurilor de pe infoarena
doar ca returneaza pozitia primului caracter din prima subsecventa a sirului a.
In caz de nu apare , se va afisa pozitia n, prima de dupa ultimul caracter al sirului a.
Indexarea incepe de pe 0
*/
#include <fstream>
#include <cstring>

using namespace std;

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

int ct=0,rez[1003];

unsigned int q = 65521; /* numarul prim < 2^16 */
unsigned int d = 257;   /* baza pentru interpretarea numerica a stringului */
unsigned int dM;        /* d^(M-1), unde M este lungimea modelului  */

void hash_init(int M) {
    dM = 1;
    for (int i = 1; i < M; i++) dM = (dM * d) % q ;
}

unsigned int hash(char* t, int n){
    unsigned h = t[0];
    for (int i = 1; i < n; i++)
        h = (d * h + t[i]) % q;
    return h;
}

unsigned int hash_next(char* t, int M, int h){
    unsigned int oldest = (dM * t[0]) % q;
    unsigned int oldest_removed = ( (h + q) - oldest ) % q;
    return (d * oldest_removed + t[M]) % q;
}

int equal_string(char* p, char* q, int n){
/* returneaza true daca primele n caractere ale lui p si q sunt identice */
    return n == 0 || ( *p == *q && equal_string(p + 1, q + 1, n - 1) );
}

void rksearch(char* p, char* a)
/*
returneaza indicele primei aparitii a sirului p in a.
returneaza lungimea sirului a daca sirul p nu apare in sirul a.
*/
{
    int M = strlen(p);
    int N = strlen(a);

    hash_init(M);
    unsigned int h1 = hash(p, M);
    unsigned int h2 = hash(a, M);
    for (char* b = a; b < a + N - M; b++)
    {
         if (h2 == h1 && equal_string(p, b, M)) rez[++ct]=b-a;
         h2 = hash_next(b, M, h2);
    }

}

int main()
{
    char *p; p=new char(2000);
    fin>>p;
    char *a; a=new char(2000);
    fin>>a;

    //fout<<p<<" "<<a<<"\n";
    rksearch(p,a);

    fout<<ct<<"\n";
    for(int i=1; i<=ct; ++i)
        fout<<rez[i]<<" ";

    return 0;
}