Cod sursa(job #1512345)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 27 octombrie 2015 22:15:26
Problema Potrivirea sirurilor Scor 92
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define MOD1 666013
#define MOD2  10001
#define x first
#define y second
#define LE 2000666
#include <vector>

bool is_match[LE];
vector<int> result;

int main()
{
    string str1,str2;
    f>>str1>>str2;
    int N1=str1.length(),N2=str2.length();
    int i;

    pair<int,int> first_hash;

    for(i=0; i<N1; ++i)
    {
        first_hash.x=(first_hash.x*26+str1[i]-'A'+1)%MOD1;
        first_hash.y=(first_hash.y*26+str1[i]-'A'+1)%MOD2;
    }

    int power_26_MOD1=1,power_26_MOD2=1;

    for(i=1; i<=N1; ++i)
    {
        power_26_MOD1=(power_26_MOD1*26)%MOD1;
        power_26_MOD2=(power_26_MOD2*26)%MOD2;
    }

    pair<int,int> second_hash;

    for(i=0; i<N2; ++i)
    {
        second_hash.x=(second_hash.x*26+(str2[i]-'A'+1) )%MOD1;
        second_hash.y=(second_hash.y*26+(str2[i]-'A'+1) )%MOD2;

        if (i>=N1)
        {
            second_hash.x=(MOD1+(second_hash.x-(str2[i-N1]-'A'+1)*power_26_MOD1)%MOD1)%MOD1;
            second_hash.y=(MOD2+(second_hash.y-(str2[i-N1]-'A'+1)*power_26_MOD2)%MOD2)%MOD2;
        }

        if (i>=N1-1&&first_hash==second_hash)    is_match[i]=true;
    }

    int sz=0;

    for(i=0; i<N2; ++i)
    {
        if (is_match[i]) ++sz;
        if (sz<=1000&&is_match[i]) result.push_back(i-N1+1);
    }
    g<<sz<<'\n';
    int N=result.size();
    for(i=0; i<N; ++i) g<<result[i]<<" ";


    return 0;
}