Cod sursa(job #2043910)

Utilizator zeboftwAlex Mocanu zeboftw Data 20 octombrie 2017 19:01:15
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <string>
#include <stdlib.h>
#include <fstream>

using namespace std;

bool match[2000001];
string s; string pattern;
ifstream fin  ("strmatch.in");
ofstream fout ("strmatch.out");

int main()
{
    fin >> pattern >> s;

    int n = s.size(), m = pattern.size();
    int long long hashpattern = 0;
    int long long hashs = 0;
    int long long firstpow = 1;
    int nr = 0;

    for (int i=1; i < m; i++) firstpow *= 73, firstpow %= 2000000011;

    for (int i=0; i < m; i++) {
        hashpattern = (hashpattern * 73 % 2000000011 + pattern[i]) % 2000000011;
    }

    for (int i=0; i < m; i++) {
        hashs = (hashs * 73 % 2000000011 + s[i]) % 2000000011;
    }

    if (hashs == hashpattern) {
        match[1] = 1;
        nr++;
    }

    for (int i=m; i < n; i++) {
        hashs = (73 * (hashs - ((int)s[i-m] * firstpow % 2000000011) % 2000000011 + 2000000011) % 2000000011 + s[i]) % 2000000011;
        if (hashs == hashpattern) {
            match[i-m+1] = 1;
            nr++;
        }
    }

    fout << nr << '\n';
    int ap = 0;
    for (int i=1; i < n && ap < 1000; i++) {
        if (match[i]) {
            fout << i << ' ';
            ap++;
        }
    }

    return 0;
}