Pagini recente » Cod sursa (job #113361) | Cod sursa (job #2060912) | Cod sursa (job #1152925) | Cod sursa (job #1231390) | Cod sursa (job #682749)
Cod sursa(job #682749)
#include<cstdio>
#include<cstring>
#include<vector>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define n_max 2000005
#define Base 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
char P[n_max], T[n_max];
vector < int > deplasament;
void citeste()
{
freopen(infile, "r", stdin);
gets(P);
gets(T);
fclose(stdin);
}
void Rabin_Karp ()
{
int N = strlen(T);
int M = strlen(P);
int HP1, HP2, HT1, HT2;
int P1, P2;
HP1 = HP2 = HT1 = HT2 = 0;
P1 = P2 = 1;
for (int i=0; i<M; ++i)
{
HP1 = (HP1 * Base + P[i]) % MOD1;
HP2 = (HP2 * Base + P[i]) % MOD2;
HT1 = (HT1 * Base + T[i]) % MOD1;
HT2 = (HT2 * Base + T[i]) % MOD2;
if(i)
{
P1 = (P1 * Base) % MOD1;
P2 = (P2 * Base) % MOD2;
}
}
for (int i=0; i <= N-M; ++i)
{
if(HT1 == HP1 && HT2 == HP2)
deplasament.push_back(i);
HT1 = (Base * (HT1 - (T[i] * P1) % MOD1) + T[i+M]) % MOD1;
HT2 = (Base * (HT2 - (T[i] * P2) % MOD2) + T[i+M]) % MOD2;
}
}
void afiseaza()
{
freopen(outfile, "w", stdout);
printf("%d\n", deplasament.size());
for(unsigned int i = 0; i < deplasament.size() && i < 1000; ++i)
printf("%d ",deplasament[i]);
printf("\n");
fclose(stdout);
}
int main()
{
citeste();
Rabin_Karp();
afiseaza();
return 0;
}