005 Potrivirea sirurilor

[•taigi100]

Ma chinui de ceva timp si nu inteleg ce nu e bine.Am incercat testele pe rand si imi dau rezultate corecte, dar evaluatorul nu imi da mai mult de 14 puncte si sincer nu pricep de ce. 

Daca se poate uita cineva peste sursa mea si sa-mi zica unde este greseala  .

http://www.infoarena.ro/job_detail/1019797

[•Sapientia]

Poate sa imi spuna cineva de ce obtin doar 40 de puncte pe sursa asta:http://www.infoarena.ro/job_detail/1093011?action=view-source?.
Pe restul testelor iau incorect.

[•vasica38]

in pascal mai mult de 40 de puncte nu se primeste 

[•klamathix]

Am schimbat limita la 0.3.

[•vasica38]

a intrat pe 100, multumesc mult

[•breahnadavid]

Bună, m-am apucat și eu să rezolv problema dar nu iau decît 16 p..
 
Deci, nu sunt sigur dacă am făcut kmp, dar am folosit functia prefix/sufix, la o dinamică pe sirul cautat, si apoi am parcurs odată sirul  in care se cauta, deci timpul O(n+m),, presupun,, nu iau TLE,, dar iau incorect.
Și nu pricep unde am greÈ™it. pe Teste mici totul e ok.  
Dar pe testele din atașamente îmi dă greșeli.. și nunțeleg, unde greșesc ....
Vă rog ajutațimăă..

Uitați și sursa.

http://www.infoarena.ro/job_detail/1198971

MULÈšUMESC ANTICIPAT..

[•Valera]

Cod:

#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string a,b;
vector<long> rez;
long i,poz=-1;

int main()
{
    getline(f,a);
    getline(f,b);

    poz=b.find(a,poz+1);
    while(poz!=string::npos)
    {
        rez.push_back(poz);
        poz=b.find(a,poz+1);
    }

    g<<rez.size()<<"\n";
    for(i=0;i<rez.size()&&i<1000;i++)
        g<<rez[i]<<" ";
    return 0;
}

Ma poate ajuta cineva sa gasesc ce am gresit ? Imi scrie Incorect la testele 13 49 si 50.

Am gasit greseala. Nu gasea daca subsirul aparea la inceput. Am initializat poz cu -1 su am luat 100 de puncte 

[•witsel]

vectorul pi reprezinta starile automatului, iar cu q doar parcurgem starile sau cum este?? ca nu am inteles foarte bine de ce nu scade q cu 1 ci se foloseste
while (q && A[q+1] != A)
            q = pi[q];
Adica am observat pe niste exemple ca asa este dar as vrea sa-mi explice cineva concret DE CE este asa.

[•retrograd]

Buna ziua! As dori putin ajutor... Am facut problema cu alg. Rabin-Karp in O(m+n), dar totusi imi da 40 de puncte. Mai mult decat atat, din testele ramase imi da TLE pe aprox. 90% din ele. Am comparat cu solutia prezentata si pot spune ca am mici optimizari, dar totusi TLE-ul e inevitabil. Daca v-ati putea uita putin pe sursa si sa imi spuneti daca vedeti ceva gresit, m-ar ajuta foarte mult. Daca nu, raman la KMP )

(ignorati rand()-ul cand generez bazele)

Sursa: http://www.infoarena.ro/job_detail/1319652?action=view-source

[•PlayLikeNeverB4]

Solutia oficiala foloseste int iar tu long long. Deci, solutia ta e mult mai inceata.

[•paftenie]

NB pentru cei ce implementeaza rabin-karp:
`long int` pe calculatorul/compilatorul pe care se ruleaza testele are doar 32 de biti; Testele oficiale functioneaza bine mersi pe calculatorul meu iar de la evaluatorul IA primesc 0 (foloseam numere mari in loc sa calculez 2 hashuri)

[•Aavatar36]

Cu  str.find()  - 100 puncte

[•Kira96]

Eu zic sa bagi str.find si la concursuri oficiale

[•petru.cehan]

Salut tuturor!
Imi spune si mie cineva ce nu e bine? Tin sa precizez ca fac putin diferit functia esec si kmp ..Pica la testele 30 31 49 50..Dar ruleaza perfect pe ele in compilatorul meu. Uitati sursa: http://www.infoarena.ro/job_detail/1452478?action=view-source

Multumesc anticipat!

[•otniel]

Cod:

void make_prefix(void)
{
    int i, q = 0;
 
    for (i = 2, pi[1] = 0; i <= M; ++i)
    {
        while (q && A[q+1] != A[i])
            q = pi[q];
        if (A[q+1] == A[i])
            ++q;
        pi[i] = q;
    }

dc intotdeauna in while() se pune q=pi[q]? Din moment ce elementele nu sunt egale de ce nu se sare direct la q=0 deoarece de acolo incepe prefixul. As vrea o explicatie si un exemplu eventual care nu functioneaza corect pe ceea ce am spus eu

[•PlayLikeNeverB4]

Incearca sa cauti "xxy" in "xxxy".

[•razvand]

http://www.infoarena.ro/job_detail/1593570

80pct verificand pentru fiecare caracter din B.

[•sulzandrei]

Oare ce gresesc la sursa asta(http://www.infoarena.ro/job_detail/1636050) folosind Rabin-Karp?

[•martons]

De ce îmi pică testele 30, 31, 49, 50 ? Le-am testat și mie mi-au ieșit corect.
http://www.infoarena.ro/job_detail/1674877

[•Bogdanisar]

Imi poate explica cineva de ce in sursa Rabin-Karp se alege baza pentru functia hash numarul 73?
Merge algoritmul si cu alte numere? Ce valori ar putea avea acestea tinand cont ca valorile sirului sunt intre 48 si 122 (0-z) ?
Conteaza ca e prim?

[•catalinlup]

Nu ma ajuta cineva?
Am incercat sa rezolv problema si cu Rabin-Karp, dar si cu KMP. Maxim am luat 40 de puncte. Nu inteleg ce e gresit.

Rabin Karp:

##########

#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000000
#define NMAX 1000
#define base 101
#define modulo 10123
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
//const int base=11;

char Cuvant[LMAX];
int CuvLen=0;
int HashCuv=0;
char String[LMAX];
int Hash=0;
int StringLen=0;
int Loc[NMAX];
int num=0;

int pow(int n,int e);

void Read(){
    in.getline(Cuvant,LMAX);
    CuvLen=strlen(Cuvant);
    in.getline(String,LMAX);
    StringLen=strlen(String);
    for(int i=0;i<CuvLen;i++){
        HashCuv+=pow(base,CuvLen-1-i)*int(Cuvant);

    }
    //HashCuv=HashCuv%modulo;
}

bool Egal(int seg){
    for(int i=0;i<CuvLen;i++){
        if(Cuvant!=String[seg+i]){
            //cout<<Cuvant<<String[seg+i]<<endl;
            return false;
        }
    }
    return true;
}

int pow(int n,int e){
    int r=1;
    for(int i=0;i<e;i++)
        r*=n;
    return r;
}

void RabinKarp(){
    Hash=0;
    for(int i=0;i<CuvLen;i++){
        int Num=pow(base,CuvLen-1-i);
        Hash=Hash+Num*int(String);
    }

    for(int i=0;i<=StringLen-CuvLen;i++){
        //cout<<Hash<<" "<<HashCuv<<endl;
        if(Hash==HashCuv){
            if(Egal(i)){
                Loc[num++]=i;
            }
        }
        Hash=base*(Hash-(double)String*pow(base,CuvLen-1))+String[i+CuvLen];
        //Hash=Hash%modulo;
    }
    out<<num<<"\n";
    for(int i=0;i<num;i++)
        out<<Loc<<" ";
}




int main()
{
    Read();
    RabinKarp();
    return 0;
}

#############

KMP:

############

#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000100
#define NMAX 1000

using namespace std;

void CrPrefTable(char pat[],int n,int P[]){
    P[0]=0;
    int border=0;
    for(int i=1;i<n;i++){
        while(border>0&&pat!=pat[border])
            border=P[border-1];
        if(pat==pat[border])
            border=border+1;
        else{
            P=0;
            border=0;
        }
        P=border;
    }
}

void KMP(char pat[],char text[]){

    int m=strlen(pat);
    int n=strlen(text);
    int Pi[m+n+1];
    char str[m+n+1];
    for(int i=0;i<m;i++)
        str=pat;
    str[m]='$';
    for(int i=0;i<n;i++){
        str[m+i+1]=text;
    }
    CrPrefTable(str,m+n+1,Pi);
    for(int i=m+1;i<m+n+1;i++){
        if(Pi==m){
            cout<<"found"<<endl;
            return;
        }
    }
    cout<<"not found"<<endl;
    return;
}
char Patt[LMAX];
char Text[LMAX];


int main()
{
    int N;
    //cin>>N;
    /*char trash[LMAX];
    cin.getline(trash,NMAX);*/
    N=1;
    cin.seekg('\n');
    for(int i=0;i<N;i++){

        cin.getline(Text,LMAX);
        cin.getline(Patt,LMAX);


        KMP(Patt,Text);
    }
    return 0;
}

#############

[•catalinlup]

Nu ma ajuta cineva?
Am incercat sa rezolv problema si cu Rabin-Karp, dar si cu KMP. Maxim am luat 40 de puncte. Nu inteleg ce e gresit.

Rabin Karp:

##########

#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000000
#define NMAX 1000
#define base 101
#define modulo 10123
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
//const int base=11;

char Cuvant[LMAX];
int CuvLen=0;
int HashCuv=0;
char String[LMAX];
int Hash=0;
int StringLen=0;
int Loc[NMAX];
int num=0;

int pow(int n,int e);

void Read(){
    in.getline(Cuvant,LMAX);
    CuvLen=strlen(Cuvant);
    in.getline(String,LMAX);
    StringLen=strlen(String);
    for(int i=0;i<CuvLen;i++){
        HashCuv+=pow(base,CuvLen-1-i)*int(Cuvant);

    }
    //HashCuv=HashCuv%modulo;
}

bool Egal(int seg){
    for(int i=0;i<CuvLen;i++){
        if(Cuvant!=String[seg+i]){
            //cout<<Cuvant<<String[seg+i]<<endl;
            return false;
        }
    }
    return true;
}

int pow(int n,int e){
    int r=1;
    for(int i=0;i<e;i++)
        r*=n;
    return r;
}

void RabinKarp(){
    Hash=0;
    for(int i=0;i<CuvLen;i++){
        int Num=pow(base,CuvLen-1-i);
        Hash=Hash+Num*int(String);
    }

    for(int i=0;i<=StringLen-CuvLen;i++){
        //cout<<Hash<<" "<<HashCuv<<endl;
        if(Hash==HashCuv){
            if(Egal(i)){
                Loc[num++]=i;
            }
        }
        Hash=base*(Hash-(double)String*pow(base,CuvLen-1))+String[i+CuvLen];
        //Hash=Hash%modulo;
    }
    out<<num<<"\n";
    for(int i=0;i<num;i++)
        out<<Loc<<" ";
}




int main()
{
    Read();
    RabinKarp();
    return 0;
}

#############

KMP:

############

#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000100
#define NMAX 1000

using namespace std;

void CrPrefTable(char pat[],int n,int P[]){
    P[0]=0;
    int border=0;
    for(int i=1;i<n;i++){
        while(border>0&&pat!=pat[border])
            border=P[border-1];
        if(pat==pat[border])
            border=border+1;
        else{
            P=0;
            border=0;
        }
        P=border;
    }
}

void KMP(char pat[],char text[]){

    int m=strlen(pat);
    int n=strlen(text);
    int Pi[m+n+1];
    char str[m+n+1];
    for(int i=0;i<m;i++)
        str=pat;
    str[m]='$';
    for(int i=0;i<n;i++){
        str[m+i+1]=text;
    }
    CrPrefTable(str,m+n+1,Pi);
    for(int i=m+1;i<m+n+1;i++){
        if(Pi==m){
            cout<<"found"<<endl;
            return;
        }
    }
    cout<<"not found"<<endl;
    return;
}
char Patt[LMAX];
char Text[LMAX];


int main()
{
    int N;
    //cin>>N;
    /*char trash[LMAX];
    cin.getline(trash,NMAX);*/
    N=1;
    cin.seekg('\n');
    for(int i=0;i<N;i++){

        cin.getline(Text,LMAX);
        cin.getline(Patt,LMAX);


        KMP(Patt,Text);
    }
    return 0;
}

#############