Pagini recente » Cod sursa (job #286039) | Cod sursa (job #1176203) | Cod sursa (job #1256645) | Cod sursa (job #564917) | Cod sursa (job #682693)
Cod sursa(job #682693)
#include<cstdio>
#include<cstring>
#include<vector>
#include<ctype.h>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define n_max 2000005
#define MOD 666013
#define d 62
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);
}
inline int numb(char c)
{
if(isdigit(c))
return c - '0';
if(isupper(c))
return c - 55;
return c - 61;
}
inline int powlog(int x, int p)
{
if (p == 0)
return 1;
int sqr = powlog(x, p/2) % MOD;
sqr = (sqr * sqr) % MOD;
if (p & 1)
sqr = 1LL* x * sqr % MOD;
return sqr;
}
void Rabin_Karp ()
{
int N = strlen(T);
int M = strlen(P);
int h = powlog(d, M-1);
int p = 0, t = 0;
for (int i=0; i<M; ++i)
{
p = (d*p + numb(P[i])) % MOD;
t = (d*t + numb(T[i])) % MOD;
}
for (int i=0; i <= N-M; ++i)
if (p == t)
{
bool gasit = 1;
for (int j=0; j<M && gasit; j++)
if (P[j] != T[i+j])
gasit = 0;
if (gasit)
deplasament.push_back(i);
}
else
t = (d*(t - ((numb(T[i])*h) % MOD)) + numb(T[i+M])) % MOD;
}
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;
}