Cod sursa(job #1262502)

Utilizator ConstantinPetroviciPetrovici Constantin ConstantinPetrovici Data 13 noiembrie 2014 11:51:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char a[2000007],b[2000007];
int MOD1=299777;
int MOD2=299771;
bool ans[2000007];

int main()
{
    cin>>a;
    cin>>b;
    int lga=strlen(a);
    int lgb=strlen(b);
    int smallhash1=0;
    int smallhash2=0;
    int putmax1=1;
    int putmax2=1;
    for ( int i = 0 ; i <= lga ; ++i )
    {
        smallhash1=(smallhash1*71+a[i])%MOD1;
        smallhash2=(smallhash2*71+a[i])%MOD2;
        if ( i )
            {
            putmax1=(putmax1*71)%MOD1;
            putmax2=(putmax2*71)%MOD2;
            }
    }
    if ( lga > lgb )
    {
        cout<<0<<'\n';
        return 0;
    }
    int bighash1=0;
    int bighash2=0;
    for ( int i = 0 ; i < lga ; ++i )
        {
            bighash1=(bighash1*71+b[i])%MOD1;
            bighash2=(bighash2*71+b[i])%MOD2;
        }
    int sol = 0 ;
    if ( smallhash1==bighash1 and smallhash2==bighash2);
    {
        ans[0]=1;
        ++sol;
    }
    for ( int i = lga ; i<= lgb ; ++i )
    {
        bighash1=(((bighash1-b[i-lga]*putmax1)%MOD1+MOD1)*71+b[i])%MOD1;
        bighash2=(((bighash2-b[i-lgb]*putmax2)%MOD2+MOD2)*71+b[i])%MOD2;
        if ( smallhash1==bighash1 and smallhash2==bighash2 )
        {
            ans[i-lga+1]=1;
            sol++;
        }
    }
    cout<<sol<<'\n';
    sol=1;
    for ( int i = 0 ; i < lgb and sol<=1000 ; ++i )
        if (ans[i]!=0)
        {
            cout<<i<<" ";
            ++sol;
        }
    cout<<'\n';
    return 0;
}