Cod sursa(job #2064645)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 12 noiembrie 2017 17:31:38
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMax = 2000005;
const int K = 256;
const int mod = 101;
char A[NMax], B[NMax];
int vp; // valoarea pattern-ului

void Read()
{
    fin >> A;
    fin >> B;
}

int Hash_Calcul(char s[])
{
    int val = (int)s[0];
    int n = strlen(s);

    for(int i = 1; i < n; ++i)
    {
        val = ((val * K + mod)%mod + (int)s[i])%mod;
    }

    return val;
}

int lgput(int nr, int po)
{
    int rez = 1;
    do
    {
        if(po & 1)
            rez = (long long)(rez * nr)%mod;

        nr = (long long)(nr*nr)%mod;

     po = po >> 1;
    }while(po);

    return rez;
}

int Checking(int i, int j)
{
    int ok = 1;

    for(int k = i; k < j && ok; ++k)
        if(B[k] != A[k-i])
            ok = 0;

    return ok;
}

char p[NMax];
int matches[NMax];

void Rabin_Karp()
{
    vp = Hash_Calcul(A);
    int np = strlen(A);
    int ns = strlen(B);
    int mtch = 0;

    int put = lgput(K,np-1);

    strncpy(p,B,np);
    int rez = Hash_Calcul(p);

    if(rez == vp)
    {
        if(Checking(0, np))
        {
            ++mtch;
            matches[mtch] = 1;
        }
    }

    for(int i = np; i < ns; ++i)
    {
        int a = (int)B[i-np];
        rez = (((rez - (a * put)%mod + mod)%mod)*K + (int)B[i])%mod;

        if(rez == vp)
        {
            if(Checking(i-np + 1,i + 1))
            {
                ++mtch;
                matches[mtch] = i - np + 1;
                if(mtch > 1000)
                    i = ns;
            }
        }
    }

    fout << mtch << "\n";

    for(int i=1; i<=min(1000,mtch); ++i)
        fout << matches[i] << " ";


}

int main()
{
    Read();
    Rabin_Karp();



    return 0;
}