Pagini recente » Cod sursa (job #1311895) | Cod sursa (job #2558561) | Cod sursa (job #1116535) | Cod sursa (job #951729) | Cod sursa (job #183392)
Cod sursa(job #183392)
#include<stdio.h>
#include<string.h>
#include<iostream.h>
#define SMAX 2000500
#define DIV1 100007
#define DIV2 100021
#define B 73
char sub[SMAX],s[SMAX];
int n_sub, n_s, i, cmp1,cmp2, hash1,hash2, b1=1,b2=1;
int poz[SMAX];
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; }
// 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; 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<=1000; i++)
printf("%d ",poz[i]);
printf("\n"); return 0; }