Pagini recente » Cod sursa (job #103199) | Cod sursa (job #430992) | Cod sursa (job #1207457) | Cod sursa (job #1596116) | Cod sursa (job #183380)
Cod sursa(job #183380)
#include<stdio.h>
#include<string.h>
#include<iostream.h>
#define SMAX 2000005
#define DIV1 100007
#define DIV2 100021
#define B 73
char sub[SMAX],s[SMAX];
long n_sub, n_s, i, cmp1,cmp2, hash1,hash2, b1=1,b2=1;
int poz[1001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s", sub, s);
n_sub = strlen(sub); n_s = strlen(s);
if(n_sub > n_s) { printf("0\n"); return 0; }
n_s = n_s - n_sub + 2 ;
// verific daca exista subsecventa cu deplasamentul i-1
for(i=0; i<n_sub; i++)
{
cmp1= (cmp1*B + sub[i]) % DIV1;
cmp2= (cmp2*B + sub[i]) % DIV2;
hash1= (hash1*B + s[i]) % DIV1;
hash2= (hash2*B + s[i]) % DIV2; if(i!=0) { b1=(b1*B) % DIV1;
b2=(b2*B) % DIV2; }
}
for(i=n_sub; i<=n_s && poz[0]<=1000; i++)
{
if(hash1==cmp1 && hash2==cmp2) poz[++poz[0]] = i - n_sub;
hash1= ( (hash1 - (s[i-n_sub]*b1) % DIV1 + DIV1) *B + s[i] ) % DIV1;
hash2= ( (hash2 - (s[i-n_sub]*b2) % DIV2 + DIV2) *B + s[i] ) % DIV2;
}
printf("%d\n",poz[0]);
for(i=1; i<=poz[0]; i++)
printf("%d ",poz[i]);
printf("\n"); return 0; }