Pagini recente » Cod sursa (job #492984) | Cod sursa (job #2614538) | Cod sursa (job #1962615) | Cod sursa (job #112772) | Cod sursa (job #1414552)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;
#define maxn 2000005
#define maxp 1005
#define X 17
#define MOD1 100003
#define MOD2 100007
#define MOD3 100005
char a[maxn], b[maxn] ;
int X1 = 1, X2 = 1, X3 = 1, hasha1, hasha2, hashb1, hashb2, hasha3, hashb3 ;
int sol[maxp] ;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", a + 1);
int na = strlen(a + 1) ;
scanf("%s\n", b + 1);
int nb = strlen(b + 1) ;
for(int i = 1; i <= na; ++i)
{
hasha1 = ( hasha1 * X + a[i] ) % MOD1 ;
hasha2 = ( hasha2 * X + a[i] ) % MOD2 ;
hasha3 = ( hasha3 * X + a[i] ) % MOD3 ;
hashb1 = ( hashb1 * X + b[i] ) % MOD1 ;
hashb2 = ( hashb2 * X + b[i] ) % MOD2 ;
hashb3 = ( hashb3 * X + b[i] ) % MOD3 ;
X1 = ( X1 * X ) % MOD1 ;
X2 = ( X2 * X ) % MOD2 ;
X3 = ( X3 * X ) % MOD3 ;
}
if( hasha1 == hashb1 && hasha2 == hashb2 )
sol[ ++sol[0] ] = 0 ;
for(int i = na + 1; i <= nb; ++i)
{
hashb1 = ( hashb1 * X + b[i] ) % MOD1 ;
hashb1 = ( hashb1 - ( b[i - na] * X1 ) % MOD1 + MOD1 ) % MOD1 ;
hashb2 = ( hashb2 * X + b[i] ) % MOD2 ;
hashb2 = ( hashb2 - ( b[i - na] * X2 ) % MOD2 + MOD2 ) % MOD2 ;
hashb3 = ( hashb3 * X + b[i] ) % MOD3 ;
hashb3 = ( hashb3 - ( b[i - na] * X3 ) % MOD3 + MOD3 ) % MOD3 ;
if( hasha1 == hashb1 && hasha2 == hashb2 && hasha3 == hashb3 )
{
++sol[0] ;
if( sol[0] > 1000 )
continue ;
sol[ sol[0] ] = i - na ;
}
}
printf("%d\n", sol[0]);
for(int i = 1; i <= min( sol[0], 1000 ); ++i )
printf("%d ", sol[i]);
return 0 ;
}