Cod sursa(job #2038037)

Utilizator zeboftwAlex Mocanu zeboftw Data 13 octombrie 2017 09:33:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <vector>

using namespace std;

vector<int> poz;
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 *= 101, firstpow %= 1999999997;

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

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

    if (hashs == hashpattern) {
        poz.push_back(1);
        nr++;
    }

    for (int i=m; i < n; i++) {
        hashs = (101 * (hashs - ((int)s[i-m] * firstpow)) % 1999999997 + s[i]) % 1999999997;
        hashs %= 1999999997;
        if (hashs == hashpattern) {
            if (s.compare(i-m+1, m, pattern) == 0) {
                poz.push_back(i - m + 1);
                nr++;
            }
        }
    }

    cout << nr << '\n';
    for (int i=0; i < nr; i++) {
        cout << poz[i] << ' ';
    }

    return 0;
}