Pagini recente » Cod sursa (job #2950952) | Cod sursa (job #2669646) | Cod sursa (job #2829659) | Cod sursa (job #641633) | Cod sursa (job #812937)
Cod sursa(job #812937)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std ;
#define maxn 2000005
#define X 71
#define mod1 100007
#define mod2 100021
#define maxsol 1001
char a[maxn], b[maxn];
int lena, lenb ;
int hasha1, hasha2 ;
int hashb1, hashb2 ;
int sol[maxsol] ;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", a + 1);
lena = strlen(a + 1);
scanf("%s\n", b + 1);
lenb = strlen(b + 1);
int X1 = 1 ;
int X2 = 1 ;
for(int i = 1; i <= lena; ++i )
{
hasha1 = (hasha1 * X + a[i] ) % mod1 ;
hasha2 = (hasha2 * X + a[i] ) % mod2 ;
X1 = ( X1 * X ) % mod1 ;
X2 = ( X2 * X ) % mod2 ;
}
for(int i = 1; i <= lena; ++i )
{
hashb1 = ( hashb1 * X + b[i] ) % mod1 ;
hashb2 = ( hashb2 * X + b[i] ) % mod2 ;
}
if( hashb1 == hasha1 && hashb2 == hasha2 )
sol[ ++sol[0] ] = 0 ;
for(int i = lena + 1; i <= lenb; ++i )
{
hashb1 = ( hashb1 * X + b[i] ) % mod1 ;
hashb2 = ( hashb2 * X + b[i] ) % mod2 ;
hashb1 = ( hashb1 - ( b[i-lena] * X1 ) % mod1 + mod1 ) % mod1 ;
hashb2 = ( hashb2 - ( b[i-lena] * X2 ) % mod2 + mod2 ) % mod2 ;
if( hashb1 == hasha1 && hashb2 == hasha2 )
{
++sol[0] ;
if( sol[0] > 1000 )
continue ;
sol[ sol[0] ] = i - lena ;
}
}
printf("%d\n", sol[0]);
for(int i = 1; i <= min(1000, sol[0]); ++i )
printf("%d ", sol[i]);
printf("\n");
return 0 ;
}