Pagini recente » Cod sursa (job #2113433) | Cod sursa (job #707799) | Cod sursa (job #954763) | Cod sursa (job #1964849) | Cod sursa (job #332747)
Cod sursa(job #332747)
//Rabin-Karp
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define N 2000001
#define mod 2000003
#define mod2 666013
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 pw255=1, i, pw2255=1;
int hp=0, h=0;
int hp2=0, h2=0;
for(i = 1; i < n; ++i)
pw255 *=255, pw255 %= mod,
pw2255 *= 255, pw2255 %= mod2;
for(i = 1; i <= n; ++i)
hp = hp * 255 + p[i], hp %= mod,
hp2 = hp2 * 255 + p[i], hp2 %= mod2;
for(i = 1; i < n; ++i)
h = h * 255 + a[i], h %= mod,
h2 = h2 * 255 + a[i], h2 %= mod2;
for(i = n; i <= m; ++i)
{
h = h * 255 + a[i], h %= mod;
h2 = h2 * 255 + a[i], h2 %= mod2;
if(h == hp)
if(h2 == hp2) if(sol.size() < 1000) sol.push_back(i-n);//printf("%d ", i-n+1);
h -= (a[i-n+1] * pw255)%mod;
h2 -= (a[i-n+1] * pw2255) % mod2;
while(h < 0) h += mod;
while(h2 < 0) h2 += mod2;
}
printf("%d\n", sol.size());
if(n <= 1000)
{
for(int i = 0; i < sol.size(); ++i) printf("%d ", sol[i]);
printf("\n");
}
else
{
for(int i = 0; i < min(1000, (int)sol.size()); ++i) printf("%d ", sol[i]);
printf("\n");
}
}
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;
}