Cod sursa(job #2078897)

Utilizator FrequeAlex Iordachescu Freque Data 30 noiembrie 2017 11:31:03
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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 putere = 1;

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

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;
        putere = (1LL * putere * BASE ) % MOD;
    }
}

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

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

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

    int cnt = 0;

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

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

    return 0;
}