Pagini recente » Cod sursa (job #2137207) | Cod sursa (job #2163017) | Cod sursa (job #2384141) | Cod sursa (job #2980372) | Cod sursa (job #332209)
Cod sursa(job #332209)
#include<stdio.h>
#include<string.h>
#define MAX_N 2000010
#define base 256
#define NR 100075
#define h(x) x % NR
#define h1(x) x % (NR-52)
int sol[1001];
int n,m,total;
char P[MAX_N],T[MAX_N];
void read(),show(),solve();
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
solve();
show();
fclose(stdin); fclose(stdout);
return 0;
}
void read()
{
scanf("%s",P);
scanf("%s",T);
n = strlen(T);
m = strlen(P);
}
void solve()
{
unsigned long long int hashPattern,hashSubstr,hashPattern1,hashSubstr1,H,H1;
int i;
if(m > n) return;
H = H1 = 1;
hashPattern = hashSubstr = hashPattern1 = hashSubstr1 =0;
for(i = 0; i < m; i++)
{
hashPattern = h(base * hashPattern + P[i]);
hashSubstr = h(base * hashSubstr + T[i]);
hashPattern1 = h1(base * hashPattern1 + P[i]);
hashSubstr1 = h1(base * hashSubstr1 + T[i]);
H = H * base;
H1 = H1 * base;
}
for(i = 0; i <= n-m+1; i++)
{
if(hashSubstr == hashPattern && hashSubstr1 == hashPattern1) //am gasit patternul
{
if(total < 1000)
{
sol[total++] = i;
}
else
{
total++;
}
}
hashSubstr = h(base * (hashSubstr - H * T[i]) + T[i+m]);
hashSubstr1 = h1(base * (hashSubstr1 - H1 * T[i]) + T[i+m]);
}
}
void show()
{
printf("%d\n",total);
for(int i = 0; i < (total > 1000 ? 1000 : total); i++)
printf("%d ",sol[i]);
}