Pagini recente » Cod sursa (job #1398542) | Cod sursa (job #1672869) | Cod sursa (job #1214736) | Cod sursa (job #677411) | Cod sursa (job #812917)
Cod sursa(job #812917)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std ;
#define maxn 2000001
#define X 26
#define mod1 666013
#define mod2 666019
char a[maxn], b[maxn] ;
int hasha1, hasha2 ;
int hash1, hash2 ;
bool ok[maxn] ;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a, b);
int lena = strlen( a ) ;
int lenb = strlen( b ) ;
if( lena > lenb )
{
printf("0\n") ;
return 0 ;
}
int X1 = 1 ;
int X2 = 1 ;
for(int i = 0; i < lena; ++i )
{
hasha1 = ( hasha1 * X + a[i] ) % mod1 ;
hasha2 = ( hasha2 * X + a[i] ) % mod2 ;
if( i > 0 )
{
X1 = ( X1 * X ) % mod1 ;
X2 = ( X2 * X ) % mod2 ;
}
hash1 = (hash1 * X + b[i]) % mod1 ;
hash2 = (hash2 * X + b[i]) % mod2 ;
}
int nr = 0 ;
if( hash1 == hasha1 && hash2 == hasha2)
{
ok[0] = true ;
++nr ;
}
for(int i = lena; i < lenb; ++i )
{
hash1 = ( ( hash1 - ( b[i-lena] * X1 ) % mod1 ) * X + b[i] ) % mod1 ;
hash2 = ( ( hash2 - ( b[i-lena] * X2 ) % mod2 ) * X + b[i] ) % mod2 ;
if( hash1 == hasha1 && hash2 == hasha2 )
{
ok[ i - lena + 1 ] = true ;
++nr ;
}
}
printf("%d\n", nr) ;
int cate = 0 ;
for(int i = 0; i < lenb; ++i )
{
if( cate > 1000 )
break ;
if( ok[i] == true )
{
++ cate ;
printf("%d ", i);
}
}
printf("\n");
return 0 ;
}