Pagini recente » Cod sursa (job #1412165) | Cod sursa (job #1308123) | Cod sursa (job #914013) | Cod sursa (job #2403702) | Cod sursa (job #458267)
Cod sursa(job #458267)
#include<fstream>
#include<string.h>
#define inf "strmatch.in"
#define outf "strmatch.out"
#define D 128
#define MOD 131
#define NMax 2000100
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
char P[NMax],T[NMax];
int N,M;
int 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
int put=1;
for(int i=1; i<=M; i++)
{
hp = ( hp*D + P[i] ) % MOD;
ht = ( ht*D + 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 ;
ht = ( ht*D + 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;
}