Cod sursa(job #1772559)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 6 octombrie 2016 20:51:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e6 + 10;
const int base = 7001;

int n, m, hash_a, hash_b, hash_bs, answer;
int pw[nmax];
vector < int > ans;

string a, b;

void print_answer(bool mode);

void read_input()
{
    fin >> a; n = (int)a.size(); a = ' ' + a;
    fin >> b; m = (int)b.size(); b = ' ' + b;

    if (n > m) print_answer(0);
}

void run_precalc()
{
    int i;

    pw[0] = 1;
    for (i = 1; i <= m; ++i)
        pw[i] = pw[i-1] * base;

    for (i = 1; i <= n; ++i)
        hash_a += pw[i] * a[i];
}

void solve()
{
    if (n > m)
        print_answer(0);

    for (int i = 1; i <= m; ++i)
    {
        hash_b += pw[i] * b[i];
        if (i < n) continue;

        if (hash_a * pw[i-n] == hash_b - hash_bs)
        {
            answer++;
            if (answer <= 1000) ans.push_back(i);
        }

        hash_bs += pw[i-n+1] * b[i-n+1];
    }

    print_answer(1);
}

void print_answer(bool mode)
{
    if (mode == 0)
        fout << 0 << '\n';
    else
    {
        fout << answer << '\n';
        for (auto it : ans) fout << it - n << ' ';
    }

    exit(0);
}


int main()
{
    read_input();
    run_precalc();
    solve();

    return 0;
}