Pagini recente » Cod sursa (job #839764) | Cod sursa (job #1593239) | Cod sursa (job #2396232) | Cod sursa (job #3223346) | Cod sursa (job #2063564)
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define MOD 101
using namespace std;
char p[NMAX], s[NMAX];
int hashSol, hashSecv, P = 256, putere = 1, sol[1005];
void hashFunction()
{
int n = strlen(p);
hashSol = p[0] % MOD;
hashSecv = s[0] % MOD;
for(int i=1; i<n; ++i)
{
hashSol = ((hashSol * P) % MOD + p[i]) % MOD;
hashSecv = (hashSecv * P + s[i]) % MOD;
putere = (putere * P) % MOD;
}
}
void cautareNaiva(int poz)
{
int n = strlen(p);
for(int i=poz, k = 0; i<poz + n; ++i, ++k)
if(p[k] != s[i])
return;
if(sol[0] < 1000)
sol[++sol[0]] = poz - n + 1;
}
void solve()
{
if(hashSol == hashSecv)
cautareNaiva(0);
int n = strlen(s), m = strlen(p);
for(int i = m; i<n; ++i)
{
hashSecv = (((hashSecv - (s[i - m]*putere) % MOD + MOD) % MOD * P)% MOD + s[i]) % MOD;
if(hashSecv == hashSol)
cautareNaiva(i);
}
}
void print()
{
printf("%d\n", hashSol);
for(int i=1; i<=sol[0]; ++i)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
//freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", &p, &s);
hashFunction();
solve();
print();
return 0;
}