Cod sursa(job #2147096)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 28 februarie 2018 14:17:15
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MOD = 100003, BAZA = 27;

string a, b;

vector<int> rest[MOD + 2];

int ans, put;
vector<int> ansPoz;

void genHash()
{
    int h = 0;
    for(int i = 0; i < a.length(); i++)
        h = ((h + BAZA * (b[i] - 'A')) * BAZA) % MOD;
    rest[h].push_back(0);

    int st = 0;
    for(int dr = a.length(); dr < b.length(); dr++)
    {
        h -= put * (b[st] - 'A');
        h = ((h + BAZA * (b[dr] - 'A')) * BAZA) % MOD;

        st++;
        rest[h].push_back(st);
    }
}

int main()
{
    in >> a >> b;

    put = BAZA;
    for(int i = 1; i <= a.length(); i++)
        put = (put * BAZA) % MOD;

    genHash();

    int ha = 0;
    for(int i = 0; i < a.length(); i++)
        ha = ((ha + BAZA * (a[i] - 'A')) * BAZA) % MOD;

    vector<int>::iterator it;
    for(it = rest[ha].begin(); it != rest[ha].end(); it++)
    {
        int poz = *it;
        bool ok = true;
        for(int i = poz; i < poz + a.length(); i++)
            if(b[i] != a[i - poz])
                ok = false;

        if(ok)
            ansPoz.push_back(poz);
    }

    out << ansPoz.size() << '\n';
    for(it = ansPoz.begin(); it != ansPoz.end(); it++)
        out << *it << ' ';
    out << '\n';

    return 0;
}