Pagini recente » Cod sursa (job #205912) | Cod sursa (job #190848) | Cod sursa (job #1087232) | Cod sursa (job #873363) | Cod sursa (job #1890956)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAX_LENGTH 2000001
#define PRIM 3
char s[MAX_LENGTH], p[MAX_LENGTH];
int sl, pl;
int ap[MAX_LENGTH];
int max_prime_power;
int power(int x,int p)
{
if(p==1) return x;
if((p&1) == 0)
{
int pt = power(x,p>>1);
return pt*pt;
}
return x*power(x,p-1);
}
void citire()
{
scanf("%s %s",p,s);
pl = strlen(p);
sl = strlen(s);
max_prime_power = power(PRIM,pl-1);
}
int compute_hash(char a[], int i, int j)
{
int prim_pow = 1, sum = 0;
for(int t = i; t<=j; t++)
{
sum += ((a[t]-'A'+1)*prim_pow);
prim_pow *= PRIM;
}
return sum;
}
int recompute_hash(int actual_hash,char a[],int i,int len)
{
int new_hash = actual_hash - (a[i-len]-'A'+1);
new_hash /= PRIM;
new_hash += (a[i]-'A'+1)*max_prime_power;
return new_hash;
}
bool is_match(int i)
{
for(int t=0;t<pl-1;t++)
if(p[t]!=s[t+i])
return false;
return true;
}
int ph, sh;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
ph = compute_hash(p,0,pl-1);
sh = compute_hash(s,0,pl-1);
for(int i = pl ; i<= sl-pl+1 ; i++)
{
sh = recompute_hash(sh,s,i,pl);
if(sh==ph && is_match(i))
{
ap[++ap[0]]=i-pl+1;
}
}
printf("%d\n",ap[0]);
for(int i=1;i<=ap[0];i++)
printf("%d ",ap[i]);
return 0;
}