Pagini recente » Istoria paginii runda/utcn_grafuri_2/clasament | Cod sursa (job #2146249) | Istoria paginii runda/numere_reale/clasament | Cod sursa (job #714967) | Cod sursa (job #332753)
Cod sursa(job #332753)
//Rabin-Karp
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define N 2000001
#define mod 2000003
using namespace std;
char a[N], p[N];
int n, m;
vector<int> sol;
inline int verify(int x, int y)
{
for(int i = x, j = 1; i <= y; ++i, ++j)
if(a[i] != p[j]) return 0;
return 1;
}
void rk()
{
int NR = 0;
int pw255=1, i;
int hp=0, h=0;
for(i = 1; i < n; ++i)
pw255 *=255, pw255 %= mod;
for(i = 1; i <= n; ++i)
hp = hp * 255 + p[i], hp %= mod;
for(i = 1; i < n; ++i)
h = h * 255 + a[i], h %= mod;
for(i = n; i <= m; ++i)
{
h = h * 255 + a[i], h %= mod;
if(h == hp)
if(verify(i-n+1, i)) if(sol.size() < 1000) sol.push_back(i-n),++NR;
else ++NR;
h -= (a[i-n+1] * pw255)%mod;
while(h < 0) h += mod;
}
printf("%d\n", NR);
for(int i = 0; i < min(1000, (int)sol.size()); ++i) printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n", &p);
scanf("%s\n", &a);
n = strlen(p);
m = strlen(a);
int i;
for(i = n; i > 0; --i) p[i] = p[i-1];
for(i = m ; i > 0;--i) a[i] = a[i-1];
rk();
return 0;
}