Pagini recente » Istoria paginii utilizator/rotaru_jeni_323cb | Monitorul de evaluare | Cod sursa (job #1377386) | Statistici Maxim Alexandru (Aly-Alexandru) | Cod sursa (job #332743)
Cod sursa(job #332743)
//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 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);//printf("%d ", i-n+1);
h -= (a[i-n+1] * pw255)%mod;
while(h < 0) h += mod;
}
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;
}