Cod sursa(job #2049033)

Utilizator MaligMamaliga cu smantana Malig Data 26 octombrie 2017 19:50:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 2e6 + 5;
const int inf = 1e9 + 5;
const int mod = 1000003;
const int base = 73;

int N,M,nrSol;
char str[NMax],patt[NMax];
int sol[NMax];

int main() {
    in>>(patt+1);
    in>>(str+1);

    int N = strlen(patt+1);
    int M = strlen(str+1);

    //cout<<patt+1<<'\n';

    ll strHash = 0, pattHash = 0, pw = 1;
    for (int i=1;i <= N;++i) {
        strHash = ((strHash*base) % mod + str[i] * base) % mod;
        pattHash = ((pattHash*base) % mod + patt[i] * base) % mod;

        pw = (pw*base) % mod;
    }

    if (pattHash == strHash) {
        sol[++nrSol] = 0;
    }

    for (int i=N+1;i <= M;++i) {
        strHash = ((strHash - ((str[i-N] * pw) % mod) + mod) * base + str[i] * base) % mod;

        if (pattHash == strHash) {
            sol[++nrSol] = i-N;
        }
    }

    out<<nrSol<<'\n';
    nrSol = min(nrSol,1000);
    for (int i=1;i <= nrSol;++i) {
        out<<sol[i]<<' ';
    }

    in.close();out.close();
    return 0;
}