Cod sursa(job #2732964)

Utilizator CatalinPangaleanuCatalin Pangaleanu CatalinPangaleanu Data 29 martie 2021 17:20:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <vector>

using namespace std;

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

const long long P=67, MOD=1000000009;

long long hash_b[2000001];

//int lps[2000001];

/*inline void getLPS(const string& a)
{   int j, i;
    j=0;
    for (i=1;i<a.size();)
        if (a[i]==a[j])
        {   ++j;
            lps[i]=j;
            ++i;
        }
        else
            if (j)
                j=lps[j-1];
            else
                ++i;
}

inline void getMatches(const string& a, const string& b)
{   vector<int> pos;
    int cnt, i, j;
    cnt=0;
    pos.reserve(1000);
    for (i=j=0;i<b.size();)
    {   if (a[j]==b[i])
            ++i, ++j;
        else
            if (j)
                j=lps[j-1];
            else
                ++i;
        if (j==a.size())
        {   ++cnt;
            if (pos.size()<1000)
                pos.push_back(i-j);
            j=lps[j-1];
        }
    }
    fout<<cnt<<'\n';
    for (i=0;i<pos.size();++i)
        fout<<pos[i]<<' ';
}*/

int main()
{   ios::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);
    int i, cnt;
    long long curr_pow, hash_a;
    string a, b;
    vector<int> pos;
    fin>>a>>b;
    fin.close();
    //getLPS(a);
    //getMatches(a, b);
    curr_pow=1;
    hash_a=0;
    for (i=0;i<a.size();++i)
    {   hash_a=(hash_a+(a[i]-'0'+1)*curr_pow%MOD)%MOD;
        curr_pow=curr_pow*P%MOD;
    }
    hash_b[0]=b[0]-'0'+1;
    curr_pow=P;
    for (i=1;i<b.size();++i)
    {   hash_b[i]=(hash_b[i-1]+(b[i]-'0'+1)*curr_pow%MOD)%MOD;
        curr_pow=curr_pow*P%MOD;
    }
    curr_pow=1;
    cnt=0;
    pos.reserve(1000);
    for (i=0;i<=(int)b.size()-(int)a.size();++i)
    {   if (hash_a*curr_pow%MOD==(hash_b[i+a.size()-1]-(i?hash_b[i-1]:0)+MOD)%MOD)
        {   ++cnt;
            if (pos.size()<1000)
                pos.push_back(i);
        }
        curr_pow=curr_pow*P%MOD;
    }
    fout<<cnt<<'\n';
    for (i=0;i<pos.size();++i)
        fout<<pos[i]<<' ';
    fout.close();

    return 0;
}