Mai intai trebuie sa te autentifici.

Cod sursa(job #2078889)

Utilizator FrequeAlex Iordachescu Freque Data 30 noiembrie 2017 11:16:32
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>

using namespace std;

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

const int BASE = 71;
const int MOD = 666013;
const int NMAX = 2000000 + 5;

queue <int> ans;
string pattern, text;
int hash_text[NMAX], hash_pattern;
int bases[NMAX];

int encrypt(char x)
{
    if (isdigit(x))
        return x;
    if ('a' <= x && x <= 'z')
        return 10 + x - 'a';
    return 36 + x - 'A';
}

void init_base()
{
    bases[0] = 1;
    for (int i = 1; i < NMAX; ++i)
        bases[i] = (1LL * bases[i - 1] * BASE) % MOD;
}

void init_hash()
{
    for (int i = 0; i < text.size(); ++i)
        hash_text[i + 1] = (1LL * hash_text[i] * BASE + encrypt(text[i])) % MOD;
    for (int i = 0; i < pattern.size(); ++i)
        hash_pattern = (1LL * hash_pattern * BASE + encrypt(pattern[i])) % MOD;
}

int subhash(int st, int dr)
{
    int aux = (hash_text[dr] - (1LL * hash_text[st - 1] * bases[dr - st + 1]) % MOD) % MOD;
    if (aux < 0)
        aux += MOD;
    return aux;
}

void read()
{
    fin >> pattern >> text;
}

int main()
{
    read();
    init_base();
    init_hash();

    int cnt = 0;

    for (int i = 0; i < text.size() - pattern.size() && cnt <= 1000; ++i)
        if (hash_pattern == subhash(i + 1, i + pattern.size()))
        {
            ans.push(i);
            ++cnt;
        }

    fout << ans.size() << '\n';
    while (!ans.empty())
    {
        fout << ans.front() << " ";
        ans.pop();
    }

    return 0;
}