Cod sursa(job #3363190)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:24:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXB = 2e6 , BZH = 67 , MODH = 1e9 + 7 , MAXI = 1e3 , BZH2 = 71 , MODH2 = 1e9 + 9;
int hb[2][MAXB + 1] , idx[MAXI + 1] , ib[2][MAXB + 1] , ha[2];
int conv ( char ch ) {
    if ( 'A' <= ch && ch <= 'Z' )
        return ch - 'A' + 1;
    else if ( 'a' <= ch && ch <= 'z' )
        return ch - 'a' + 27;
    else
        return ch - '0' + 53;
}
int mypow ( int b , int e , int mod ) {
    int rez;

    rez = 1;
    while ( e > 0 ) {
        if ( e % 2 == 1 )
            rez = ( long long ) rez * b % mod;
        b = ( long long ) b * b % mod;
        e = e / 2;
    }

    return rez;
}
int get ( int dr , int st ) {
    return ( hb[0][dr] - hb[0][st - 1] + MODH ) % MODH * ( long long ) ib[0][st - 1] % MODH;
}
int get1 ( int dr , int st ) {
    return ( hb[1][dr] - hb[1][st - 1] + MODH2 ) % MODH2 * ( long long ) ib[1][st - 1] % MODH2;
}

void calcPb () {
    int i , pb;

    pb = 1;
    for ( i = 1 ; i <= MAXB ; i++ )
        pb = ( long long ) pb * BZH % MODH;
    ib[0][MAXB] = mypow ( pb , MODH - 2 , MODH );
    for ( i = MAXB - 1 ; i >= 0 ; i-- )
        ib[0][i] = ( long long ) ib[0][i + 1] * BZH % MODH;
    pb = 1;
    for ( i = 1 ; i <= MAXB ; i++ )
        pb = ( long long ) pb * BZH2 % MODH2;
    ib[1][MAXB] = mypow ( pb , MODH2 - 2 , MODH2 );
    for ( i = MAXB - 1 ; i >= 0 ; i-- )
        ib[1][i] = ( long long ) ib[1][i + 1] * BZH2 % MODH2;
}
signed main () {
    ifstream fin ( "strmatch.in" );
    ofstream fout ( "strmatch.out" );
    char la , lb;
    int lenb , lena , i , leni , pb1 , pb2;

    calcPb ();
    fin.get ( la );
    lena = 0;
    pb1 = pb2 = 1;
    while ( la != '\n' ) {
        ha[0] = ( ha[0] + ( long long ) conv ( la ) * pb1 % MODH ) % MODH;
        ha[1] = ( ha[1] + ( long long ) conv ( la ) * pb2 % MODH2 ) % MODH2;
        pb1 = ( long long ) pb1 * BZH % MODH;
        pb2 = ( long long ) pb2 * BZH2 % MODH2;
        lena++;
        fin.get ( la );
    }
    fin.get ( lb );
    lenb = pb1 = pb2 = 1;
    while ( lb != '\n' ) {
        hb[0][lenb] = ( hb[0][lenb - 1] + ( long long ) conv ( lb ) * pb1 % MODH ) % MODH;
        hb[1][lenb] = ( hb[1][lenb - 1] + ( long long ) conv ( lb ) * pb2 % MODH2 ) % MODH2;
        pb1 = ( long long ) pb1 * BZH % MODH;
        pb2 = ( long long ) pb2 * BZH2 % MODH2;
        lenb++;
        fin.get ( lb );
    }
    lenb--;
    leni = 0;
    for ( i = lena ; i <= lenb ; i++ )
        if ( get ( i , i - lena + 1 ) == ha[0] && get1 ( i , i - lena + 1 ) == ha[1] ) {
            leni++;
            if ( leni <= MAXI )
                idx[leni] = i - lena;
        }
    fout << leni << '\n';
    for ( i = 1 ; i <= min ( leni , MAXI ) ; i++ )
        fout << idx[i] << ' ';
    fout.put ( '\n' );
    return 0;
}