Pagini recente » Cod sursa (job #1079380) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 128 | Cod sursa (job #2880770) | Cod sursa (job #2112468) | Cod sursa (job #332348)
Cod sursa(job #332348)
#include<stdio.h>
#include<string.h>
#define MAX_N 2000010
#define base 256
#define NR 100075
#define h(x) x % NR
int sol[1001];
int n,m,total;
char P[MAX_N],T[MAX_N];
unsigned int hashPattern,hashSubstr,H;
int i;
inline int egal(int k)
{
int i;
for(i = 0; i < m; i++)
if(P[i] != T[k+i]) return 0;
return 1;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",P);
scanf("%s",T);
n = strlen(T);
m = strlen(P);
if(m > n) { printf("0\n"); return 0; }
H = 1;
for(i = 0; i < m; i++)
{
hashPattern = h(base * hashPattern + P[i]);
hashSubstr = h(base * hashSubstr + T[i]);
H = H * base;
}
for(i = 0; i <= n-m+1; i++)
{
if(hashSubstr == hashPattern) //am gasit patternul
{
if(egal(i)) //ne asiguram ca nu avem coliziune
{
if(total < 1000)
{
sol[total++] = i;
}
else
{
total++;
}
}
}
hashSubstr = h(base * (hashSubstr - H * T[i]) + T[i+m]);
}
printf("%d\n",total);
for(i = 0; i < (total > 1000 ? 1000 : total); i++)
printf("%d ",sol[i]);
fclose(stdin); fclose(stdout);
return 0;
}