Pagini recente » Cod sursa (job #501621) | Cod sursa (job #685726) | Cod sursa (job #28188) | Cod sursa (job #1699301) | Cod sursa (job #1409496)
///Rabin-Karp ALGORITHM
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define ull unsigned int
using namespace std;
const int NMAX = 2000004;
const int Base = 53;
char a[NMAX], b[NMAX];
int sol[1004], lg, n, m;
ull Pow[NMAX], H[NMAX];
inline void Solve()
{
ull Codif=0;
for(int i=1;i<=n;++i)
Codif = Codif*Base+a[i]-'A';
Pow[0] = 1;
for(int i=1;i<=m;++i)
{
H[i] = H[i-1]*Base+b[i]-'A';
Pow[i] = Pow[i-1]*Base;
if(i >= n)
{
ull x = H[i]-Pow[n]*H[i-n];
if(x==Codif)
{
++lg;
if(lg<=1000)
sol[lg] = i-n;
}
}
}
}
inline void Write()
{
printf("%d\n",lg);
lg = min(lg,1000);
for(int i=1;i<=lg;++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",(a+1),(b+1));
n = strlen(a+1), m = strlen(b+1);
Solve();
Write();
return 0;
}