Pagini: 1 2 [3]   În jos
  Imprimă  
Ajutor Subiect: 005 Potrivirea sirurilor  (Citit de 38405 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
taigi100
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #50 : Octombrie 31, 2013, 22:27:49 »

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.  Angry

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

http://www.infoarena.ro/job_detail/1019797
Memorat
Sapientia
Strain
*

Karma: 0
Deconectat Deconectat

Mesaje: 29



Vezi Profilul
« Răspunde #51 : Ianuarie 27, 2014, 17:55:15 »

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.
Memorat
vasica38
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #52 : Aprilie 15, 2014, 16:53:23 »

in pascal mai mult de 40 de puncte nu se primeste  Whistle
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #53 : Aprilie 15, 2014, 23:24:20 »

Am schimbat limita la 0.3.
Memorat
vasica38
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #54 : Aprilie 20, 2014, 20:33:22 »

a intrat pe 100, multumesc mult Ok
Memorat
breahnadavid
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 15



Vezi Profilul
« Răspunde #55 : Iunie 17, 2014, 19:55:11 »

Bună, m-am apucat și eu să rezolv problema dar nu iau decît 16 p..
 Brick wall Brick wall Brick wall Fighting Fighting
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.  Ok Ok
Dar pe testele din atașamente îmi dă greșeli.. și nunțeleg, unde greșesc .... Brick wall Brick wall Brick wall Fighting Fighting
Vă rog ajutațimăă..

Uitați și sursa.

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

MULȚUMESC ANTICIPAT.. peacefingers peacefingers
Memorat
Valera
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #56 : August 11, 2014, 13:19:58 »

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  Very Happy
Memorat
witsel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 15



Vezi Profilul
« Răspunde #57 : Decembrie 06, 2014, 19:01:21 »

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.
Memorat
retrograd
Client obisnuit
**

Karma: 3
Deconectat Deconectat

Mesaje: 50



Vezi Profilul
« Răspunde #58 : Ianuarie 17, 2015, 12:09:50 »

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 Smile)

(ignorati rand()-ul cand generez bazele)

Sursa: http://www.infoarena.ro/job_detail/1319652?action=view-source
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #59 : Ianuarie 17, 2015, 14:05:09 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #60 : Martie 01, 2015, 23:54:22 »

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)
Memorat
Aavatar36
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #61 : Aprilie 13, 2015, 14:25:32 »

Cu  str.find()  - 100 puncte Very Happy
Memorat
Kira96
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #62 : Mai 13, 2015, 00:49:03 »

Eu zic sa bagi str.find si la concursuri oficiale
Memorat
petru.cehan
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #63 : Iunie 20, 2015, 22:38:30 »

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!
Memorat
otniel
Strain
*

Karma: -13
Deconectat Deconectat

Mesaje: 49



Vezi Profilul
« Răspunde #64 : August 07, 2015, 14:16:55 »

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
« Ultima modificare: August 07, 2015, 15:00:10 de către Savin Tiberiu » Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #65 : August 23, 2015, 22:11:08 »

Incearca sa cauti "xxy" in "xxxy".
Memorat
razvand
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #66 : Februarie 08, 2016, 18:32:29 »

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

80pct verificand pentru fiecare caracter din B.
Memorat
sulzandrei
Strain
*

Karma: -3
Deconectat Deconectat

Mesaje: 28



Vezi Profilul
« Răspunde #67 : Martie 06, 2016, 22:04:44 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #68 : Aprilie 04, 2016, 21:09:48 »

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
Memorat
Bogdanisar
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #69 : Februarie 09, 2017, 16:46:10 »

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?
« Ultima modificare: Februarie 09, 2017, 17:20:07 de către Burcea Bogdan Madalin » Memorat
catalinlup
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #70 : Iulie 03, 2017, 15:35:13 »

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;
}

#############
Memorat
catalinlup
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #71 : Iulie 03, 2017, 15:35:53 »

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;
}

#############
Memorat
Pagini: 1 2 [3]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines