Pagini recente » Cod sursa (job #588033) | Cod sursa (job #1418396) | Cod sursa (job #2191982) | Cod sursa (job #327247) | Cod sursa (job #332098)
Cod sursa(job #332098)
#include<stdio.h>
#include<string>
#define MAX_N 2000000
#define base 256
#define NR 100023
#define h(x) x % NR
char T[MAX_N],P[MAX_N];
int sol[1001];
int n,m,total;
void read(),show(),solve();
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
if(m > n)
{
printf("0\n");
return 0;
}
solve();
show();
fclose(stdin); fclose(stdout);
return 0;
}
void read()
{
scanf("%s",P);
scanf("%s",T);
n = strlen(T);
m = strlen(P);
}
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;
H = 1;
hashPattern = hashSubstr = 0;
for(i = 0; i < m; i++)
{
hashPattern = h(base * hashPattern + P[i]);
hashSubstr = h(base * hashSubstr + T[i]);
if(i) H = 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]);
}