Cod sursa(job #2732259)

Utilizator octavi26octavian octavi26 Data 28 martie 2021 20:42:56
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define N 2000008
#define mod 1000000007

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[N];
char b[N];
long long H[2][N];
int n, m;

void Citire()
{
    fin >> a;
    n = strlen( a );
    fin >> b;
    m = strlen( b );
}

long long P[N];

void createHash()
{
    int i;
    H[0][0] = a[0];
    for( i=1; i<n; i++ )
        H[0][i] = ( ( H[0][i - 1] * 26 ) % mod + a[i] ) % mod;

    H[1][0] = b[0];
    for( i=1; i<m; i++ )
        H[1][i] = ( ( H[1][i - 1] * 26 ) % mod + b[i] ) % mod;
}

vector<int> sol;

void Rezolvare()
{
    int i;
    P[0] = 1;
    for( i=1; i<=max( n, m ); i++ )
        P[i] = ( P[i - 1] * 26 ) % mod;
    createHash();

    if( n > m )
    {
        fout << "0";
        return;
    }

    int ct = 0;
    for( i=n - 1; i<m; i++ )
    {
        long long Hash = ( H[1][i] + mod - ( (i - n < 0 ? 0 : H[1][i - n]) * P[n] ) % mod ) % mod;
        if( H[0][n-1] == Hash ) ct++, sol.push_back( i - n + 1 );
    }

    fout << ct << "\n";
    ct = 0;
    for( auto e : sol )
    {
        ct++;
        if( ct > 1000 ) return;
        fout << e << " ";
    }
}

int main()
{
    Citire();
    Rezolvare();
    fin.close();
    fout.close();
    return 0;
}