Pagini recente » Clasament Teme ACM Unibuc 2013 | Cod sursa (job #1606459) | Cod sursa (job #3190773) | Cod sursa (job #149862) | Cod sursa (job #458268)
Cod sursa(job #458268)
#include<fstream>
#include<string.h>
#define inf "strmatch.in"
#define outf "strmatch.out"
#define D 73
#define MOD 666013
#define NMax 2000100
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
char P[NMax],T[NMax];
int N,M;
long long hp,ht;
int nr,sol[NMax];
void read()
{
f.get( P+1, NMax );
f.get();
f.get( T+1, NMax );
M = strlen( P+1 );
N = strlen( T+1 );
}
bool egal( char P[], char T[], int poz, int dim )
{
int j=1;
for(int i=poz; i<poz+dim; i++)
if( P[j++] != T[i] ) return false;
return true;
}
void solve()
{
//preprocesare pattern
long long put=1;
for(int i=1; i<=M; i++)
{
hp = ( (hp*D)%MOD + P[i] ) % MOD;
ht = ( (ht*D)%MOD + T[i] ) % MOD;
if( i!=M ) put = ( put*D ) % MOD;
}
//matching
for(int i=1; i<=N-M+1; i++)
{
if( hp==ht && egal(P,T,i,M) ) sol[++nr] = i-1;
ht = ( ( ht - (put*T[i])%MOD ) % MOD + MOD ) % MOD ;
ht = ( (ht*D)%MOD + T[i+M] ) % MOD;
}
g<< nr <<"\n";
for(int i=1; i<=nr; i++) g<< sol[i] <<" ";
}
int main()
{
read(); solve();
f.close(); g.close();
return 0;
}