Cod sursa(job #2723175)

Utilizator Rares09Rares I Rares09 Data 13 martie 2021 18:58:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <vector>
#include <string>
#define MOD1 1000000007
#define MOD2 1000000009
#define P 179
#define fi first
#define se second

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

int finds, p1 = 1, p2 = 1, v[2000005];
vector <int> sol;
string pattern, s;

pair <long long, long long> genHash()
{
    long long hash1 = 0, hash2 = 0;

    for(auto it = pattern.begin(); it != pattern.end(); ++it)
    {
        hash1 = (((hash1 * P) % MOD1) + *it) % MOD1;
        hash2 = (((hash2 * P) % MOD2) + *it) % MOD2;

        if(it != pattern.begin())
        {
            p1 = (p1 * P) % MOD1;
            p2 = (p2 * P) % MOD2;
        }
    }

    return {hash1, hash2};
}



int main()
{
    getline(cin, pattern);
    getline(cin, s);
    pair <long long, long long> ogh = genHash();
    pair <long long, long long> amh;
    int n = s.length();
    int m = pattern.length();

    for(auto i = 0; i < n; ++i)
    {
        if(i >= m)
        {
            amh.fi = 1ll * ((((amh.fi + MOD1 - (s[i - m] * p1) % MOD1) * P) % MOD1) + s[i]) % MOD1;
            amh.se = 1ll * ((((amh.se + MOD2 - (s[i - m] * p2) % MOD2) * P) % MOD2) + s[i]) % MOD2;
        }
        else
        {
            amh.fi = 1ll * (((amh.fi * P) % MOD1) + s[i]) % MOD1;
            amh.se = 1ll * (((amh.se * P) % MOD2) + s[i]) % MOD2;
        }

        if(amh == ogh)
        {
            ++finds;

            if(finds <= 1000)
                sol.push_back(i - m + 1);
        }
    }

    cout << finds << '\n';

    for(auto it = sol.begin(); it != sol.end(); ++it)
        cout << *it << ' ';

    cout << '\n';
    return 0;
}