Pagini recente » Cod sursa (job #596032) | Cod sursa (job #2360161) | Cod sursa (job #2943020) | Cod sursa (job #1236660) | Cod sursa (job #2591475)
#include<cstdio>
#include<cstring>
const int NMAX = 2000000;
const int MOD1 = 1000159;
const int MOD2 = 1000033;
char a[NMAX + 1];
char b[NMAX + 1];
char v[NMAX + 1];
int main()
{
int k = 0;
freopen("strmatch.in" , "r" , stdin);
freopen("strmatch.out" , "w" , stdout);
scanf("%s" , a);
int n = strlen(a);
scanf("%s" , b);
int m = strlen(b);
int putere1 = 76;
int putere2 = 83;
int p1 = 1;
int p2 = 1;
int hashA1 = a[0] - '0';
int hashA2 = a[0] - '0';
int hashB1 = b[0] - '0';
int hashB2 = b[0] - '0';
for(int i = 1; i < n ; i ++)
{
hashA1 = hashA1 * putere1 + (a[i] - '0') % MOD1;
hashA2 = hashA2 * putere2 + (a[i] - '0') % MOD2;
hashB1 = hashB1 * putere1 + (b[i] - '0') % MOD1;
hashB2 = hashB2 * putere2 + (b[i] - '0') % MOD2;
p1 = p1 * putere1 % MOD1;
p2 = p2 * putere2 % MOD2;
}
for(int i = 1; i + n - 1 < m ; i ++)
{
hashB1 = ((hashB1 - (b[i - 1] - '0') * p1 + MOD1) % MOD1 * putere1 % MOD1 + (b[i + n - 1] - '0')) % MOD1;
hashB2 = ((hashB2 - (b[i - 1] - '0') * p2 + MOD2) % MOD2 * putere2 % MOD2 + (b[i + n - 1] - '0')) % MOD2;
if(hashA1 == hashB1 && hashB2 == hashA2)
{
v[++k] = i;
}
}
printf("%d\n" , k);
for(int i = 1; i <= k && i <= 1000 ; i ++)
printf("%d " , v[i]);
return 0;
}