Cod sursa(job #2078916)

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

using namespace std;

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

const int BASE1 = 73;
const int BASE2 = 79;
const int MOD1 = 666013;
const int MOD2 = 1000000007;
const int NMAX = 2000000 + 5;

queue <int> ans;
string pattern, text;
int hash_text1, hash_pattern1;
int hash_text2, hash_pattern2;

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 < pattern.size(); ++i)
        hash_pattern1 = (1LL * hash_pattern1 * BASE1 + encrypt(pattern[i])) % MOD1;
    for (int i = 0; i < pattern.size(); ++i)
        hash_pattern2 = (1LL * hash_pattern2 * BASE2 + encrypt(pattern[i])) % MOD2;
}

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

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

    int cnt = 0, put1 = 1, put2 = 1;
    for (int i = 0; i < pattern.size(); i++)
    {
        put1 = (1LL * put1 * BASE1) % MOD1;
        put2 = (1LL * put2 * BASE2) % MOD2;
    }

    for (int i = 0; i < text.size(); ++i)
    {
        hash_text1 = (1LL * hash_text1 * BASE1 + encrypt(text[i])) % MOD1;
        hash_text2 = (1LL * hash_text2 * BASE2 + encrypt(text[i])) % MOD2;
        if (i >= pattern.size())
        {
            hash_text1 -= (1LL * encrypt(text[i - pattern.size()]) * put1) % MOD1;
            hash_text2 -= (1LL * encrypt(text[i - pattern.size()]) * put2) % MOD2;
        }
        if (hash_text1 < 0) hash_text1 += MOD1;
        if (hash_text2 < 0) hash_text2 += MOD2;

        if (i >= pattern.size() - 1 && hash_pattern1 == hash_text1 && hash_pattern2 == hash_text2)
        {
            ++cnt;
            if (cnt <= 1000) ans.push(i - pattern.size() + 1);
        }
    }

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

    return 0;
}