Cod sursa(job #2049738)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 27 octombrie 2017 16:36:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
#define NMAX 2000005
 
#define MOD1 10007
#define MOD2 666013
#define NR1 79
#define NR2 73
using namespace std;
 
char a[NMAX], b[NMAX];
int n, m, v1, v2, h1, h2, pow1 = 1, pow2 = 1, nr;
bitset<NMAX> match;
 
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
 
    gets(a);
    gets(b);
    n = strlen(a);
    m = strlen(b);
 
    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)
    {
        match[0]=1;
        ++nr;
    }
 
    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)
        {
            match[i-n+1]=1;
            ++nr;
        }
    }
 
    printf("%d\n",nr);
 
    nr = 0;
 
    for(int i=0;i < m && nr <1000;i++)
        if(match[i])
        {
            ++nr;
            printf("%d ",i);
        }
 
 
    return 0;
}