Pagini recente » Cod sursa (job #645830) | Cod sursa (job #2302643) | Cod sursa (job #933332) | Cod sursa (job #771409) | Cod sursa (job #332117)
Cod sursa(job #332117)
#include<stdio.h>
#include<string.h>
#define MAX_N 2000000
#define base 256
#define NR 100023
#define h(x) x % NR
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);
m = strlen(P);
n = strlen(T);
}
int egal(int k)
{
int i;
for(i = 0; i < m; i++)
if(P[i] != T[k+i]) return 0;
return 1;
}
void solve()
{
unsigned long long int hashPattern,hashSubstr,H;
int i;
if(m > n) return;
H = 1; h(putere(base,m-1));
hashPattern = hashSubstr = 0;
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; 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]);
}
}
void show()
{
printf("%d\n",total);
for(int i = 0; i < (total > 1000 ? 1000 : total); i++)
printf("%d ",sol[i]);
}