Cod sursa(job #2084076)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 8 decembrie 2017 17:11:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#define DM 2000001
#include <fstream>
using namespace std;

ifstream fi ("strmatch.in");
ofstream fo ("strmatch.out");
int cnt, pos[DM], n, m, pt[DM], hsc, hs;
string a, b;

int main()
{
    fi >> a >> b;
    n = a.size();
    m = b.size();
    pt[0] = 1;
    for (int i = 1; i <= n; ++i)
        pt[i] = pt[i-1]*29;
    for (int i = 0; i < n; ++i)
        hs+=(a[i] - '0')*pt[i];
    for (int i = 0; i < n; ++i)
        hsc+=(b[i] - '0')*pt[i];
    if (hsc == hs)
        pos[++cnt] = 0;
    for (int i = n; i < m && cnt <= 1000; ++i)
    {
        hsc/=29;
        hsc+=(b[i] - '0')*pt[n-1];
        if (cnt <= 1000 && hsc == hs)
            pos[++cnt] = i - n + 1;
    }
    fo << cnt << '\n';
    for (int i = 1; i <= cnt; ++i)
        fo << pos[i] << ' ';
    return 0;
}