Cod sursa(job #1410009)

Utilizator httpsLup Vasile https Data 30 martie 2015 20:08:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

#ifdef INFOARENA
ifstream f("strmatch.in");
#define cout g
#else
ifstream f("date.in");
#endif // INFOARENA

ofstream g("strmatch.out");

#define nmax 2000001
#define MOD1 999981
#define MOD2 999983
#define nr(a) (a-'0')
#define BASE 75

char A[nmax],B[nmax];
int pref[nmax],n,m,k,pos,i,hash1_A,hash2_A,hash1_B,hash2_B,P1,P2;
vector <int> sol;


int main()
    {
    f>>A+1>>B+1;
    n=strlen(A+1);
    m=strlen(B+1);

    if(m<n)
    {
        cout<<0;
        return 0;
    }
    P1=P2=1;
    for(i=1;i<=n;++i)
    {
        hash1_A = (hash1_A * BASE + nr(A[i])) % MOD1;
        hash2_A = (hash2_A * BASE + nr(A[i])) % MOD2;

        hash1_B = (hash1_B * BASE + nr(B[i])) % MOD1;
        hash2_B = (hash2_B * BASE + nr(B[i])) % MOD2;


        if(i>1)
        {
            P1 =1ll*P1 * BASE % MOD1;
            P2 =1ll*P2 * BASE % MOD2;
        }
    }

    if(hash1_A==hash1_B && hash2_A == hash2_B) sol.push_back(0);

    for(i=n+1;i<=m;++i)
    {
        hash1_B =1ll*((hash1_B - 1ll*nr(B[i-n]) * P1 % MOD1 + MOD1) * BASE + nr(B[i])) % MOD1;
        hash2_B =1ll*((hash2_B - 1ll*nr(B[i-n]) * P2 % MOD2 + MOD2) * BASE + nr(B[i])) % MOD2;


        if(hash1_A==hash1_B && hash2_A == hash2_B) sol.push_back(i-n);

    }
    int x=0;
    cout<<sol.size()<<'\n';
    for(auto i:sol)
    {
        cout<<i<<' ';
        if(++x>=1000) break;
    }
    return 0;
    }