Cod sursa(job #2127071)

Utilizator MaligMamaliga cu smantana Malig Data 10 februarie 2018 12:07:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

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

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
const int NMax = 2e6 + 5;
const int inf = 1e9 + 5;
const int mod1 = 1000003;
const int mod2 = 10003;
const int base = 73;
using zint = int;

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

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

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

    int pattHash1 = 0, pattHash2 = 0, pw1 = 1, pw2 = 1;
    int strHash1 = 0, strHash2 = 0;
    for (int i = 1;i <= N;++i) {
        pattHash1 = (pattHash1 * base + (patt[i] - '0') * base) % mod1;
        pattHash2 = (pattHash2 * base + (patt[i] - '0') * base) % mod2;

        strHash1 = (strHash1 * base + (str[i] - '0') * base) % mod1;
        strHash2 = (strHash2 * base + (str[i] - '0') * base) % mod2;

        pw1 = (pw1 * base) % mod1;
        pw2 = (pw2 * base) % mod2;
    }

    if (strHash1 == pattHash1 && strHash2 == pattHash2) {
        sol[++nrSol] = 0;
    }

    for (int i = N+1;i <= M;++i) {
        //*
        strHash1 = ((strHash1 - (pw1 * (str[i-N] - '0')) % mod1 + mod1) * base + (str[i]-'0') * base) % mod1;
        strHash2 = ((strHash2 - (pw2 * (str[i-N] - '0')) % mod2 + mod2) * base + (str[i]-'0') * base) % mod2;
        //*/

        if (strHash1 == pattHash1 && strHash2 == pattHash2) {
            sol[++nrSol] = i - N;
        }
    }

    //cout<<(int)'0'<<' '<<(int)'0';

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

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