Cod sursa(job #2143095)

Utilizator rnqftwcalina florin daniel rnqftw Data 25 februarie 2018 16:23:40
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

#define MOD1 10007
#define MOD2 666013
#define NR1 79
#define NR2 73
using namespace std;

string a,b;
int n, m, v1, v2, h1, h2, pow1 = 1, pow2 = 1, nr;
vector <int> sol;

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in>>a>>b;
    in.close();
    n = a.size();
    m = b.size();

    if(n>m)
    {
        printf("0\n");
        return 0;
    }

    v1 = v2 = 0;

    for(int i=0; i<n; ++i)
    {
        v1 = (1LL * v1 * NR1 + a[i]) % MOD1;
        v2 = (1LL * v2 * NR2 + a[i]) % MOD2;

        if(i)
        {
            pow1 =(pow1 * NR1) % MOD1;
            pow2 =(pow2 * NR2) % MOD2;
        }

        h1 = (1LL * h1 * NR1 + b[i]) % MOD1;
        h2 = (1LL * h2 * NR2 + b[i]) % MOD2;
    }

    if(h1==v1 && h2==v2)
    {
        sol.push_back(0);
    }

    for(int i=n;i<m;i++)
    {
        h1 = ((h1 - (b[i-n]*pow1) % MOD1 + MOD1)* NR1 + b[i]) % MOD1;
        h2 = ((h2 - (b[i-n]*pow2) % MOD2 + MOD2)* NR2 + b[i]) % MOD2;

        if(h1==v1 && h2==v2)
        {
            sol.push_back(i-n+1);
        }
    }

    out<<sol.size()<<'\n';
    int lim=min(1000,(int)sol.size());
    for(int i=0;i < lim ;i++)
        {
         out<<sol[i]<<" ";
        }


    return 0;
}