Cod sursa(job #2368705)

Utilizator FrequeAlex Iordachescu Freque Data 5 martie 2019 17:21:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define enter cout << '\n'

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <ll> vl;
typedef vector <pll> vll;
typedef queue <int> qi;
typedef queue <pii> qii;
typedef queue <ll> ql;
typedef queue <pll> qll;

const int INF = 0x3f3f3f3f;
const int MOD = 100003;
const int MOD1 = 1e5 + 7;
const int MOD2 = 1e5 + 21;
const int BASE = 73;
const double EPSILON = 1e-10;
const int NMAX = 5e4 + 5;

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

string pattern, text;
int hash_p1, hash_p2, hash_t1, hash_t2, base1 = 1, base2 = 1;
vi ans;

int main()
{
    fin >> pattern >> text;

    if ((int)pattern.size() > (int)text.size())
    {
        fout << "0\n";
        return 0;
    }

    for (int i = 0; i < (int)pattern.size(); ++i)
    {
        hash_p1 = (hash_p1 * BASE + pattern[i]) % MOD1;
        hash_p2 = (hash_p2 * BASE + pattern[i]) % MOD2;

        if (i != 0)
        {
            base1 = (base1 * BASE) % MOD1;
            base2 = (base2 * BASE) % MOD2;
        }
    }

    for (int i = 0; i < (int)pattern.size(); ++i)
    {
        hash_t1 = (hash_t1 * BASE + text[i]) % MOD1;
        hash_t2 = (hash_t2 * BASE + text[i]) % MOD2;
    }

    if (hash_p1 == hash_t1 && hash_p2 == hash_t2)
        ans.pb(0);

    for (int i = (int)pattern.size(); i < (int)text.size(); ++i)
    {
        hash_t1 = (((hash_t1 - (text[i - (int)pattern.size()] * base1) % MOD1 + MOD1) * BASE) % MOD2 + text[i]) % MOD1;
        hash_t2 = (((hash_t2 - (text[i - (int)pattern.size()] * base2) % MOD2 + MOD2) * BASE) % MOD2 + text[i]) % MOD2;

        if (hash_p1 == hash_t1 && hash_p2 == hash_t2)
            ans.pb(i - (int)pattern.size() + 1);
    }

    fout << ans.size() << '\n';
    for (int i = 0; i < 1000; ++i)
        fout << ans[i] << ' ';

    return 0;
}