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

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

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

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