Cod sursa(job #2589887)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 27 martie 2020 09:23:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MOD = 1e9 + 9;
const int base = 256;

int putere(int x, int p)
{
    int aux = 1;

    while (p)
    {
        if (p % 2)
            aux = (1ll * aux * x) % MOD;
        x = (1ll * x * x) % MOD;
        p /= 2;
    }
    return aux;
}

char s[2000005], p[2000005];
int hp, hs;
vector<int> sol;

int main()
{
    cin >> p >> s;
    int np = strlen(p);
    for (int i = 0; i < np; i++)
    {
        hp = (1ll * hp * base + p[i]) % MOD;
        hs = (1ll * hs * base + s[i]) % MOD;
    }
    int ns = strlen(s);
    int pBase = putere(base, np - 1);
    for (int i = 0; i < ns - np + 1; i++)
    {
        if (i != 0)
        {
            hs -= (1ll * s[i - 1] * pBase) % MOD;
            hs = (hs + MOD) % MOD;
            hs = (1ll * hs * base) % MOD;
            hs = (hs + s[i + np - 1]) % MOD;
        }
        if (hs == hp)
        {
            int ok = 1;
            for (int j = i; j < i + np; j++)
            {
                if (s[j] != p[j-i])
                {
                    ok = 0;
                    break;
                }
            }
            if (ok)
                sol.push_back(i);
            if (sol.size() == 1000)
                break;
        }
    }
    cout << sol.size() << '\n';
    for (int i : sol)
        cout << i << ' ';
    return 0;
}