Pagini recente » template/preoni-2008/header | Istoria paginii runda/labareala | Cod sursa (job #2006035) | Statistici Alexia Diaconu (alexia_diaconu07) | Cod sursa (job #1482869)
#include<stdio.h>
#include<string.h>
#define MAX 2000001
#define d 256
int count;
int poz[MAX];
char pat[MAX],txt[MAX];
void search(char* pat,char* txt,int q /*nr prim*/)
{
int M=strlen(pat);
int N=strlen(txt);
int i,j,p=0 /*hash-ul pt pattern*/,t=0 /*hash-ul pt txt*/,h=1;
for(i=0;i<M-1;i++)
h=(h*d)%q;
for(i=0;i<M;i++)
{
p=(p*d+pat[i])%q;
t=(t*d+txt[i])%q;
}
for(i=0;i<=N-M;i++)
{
if(p==t)
{
for(j=0;j<M;j++)
if(txt[i+j]!=pat[j])
break;
if(j==M)
{
poz[count]=i;
count++;
}
}
if(i<N-M)
{
t=(d*(t-txt[i]*h)+txt[i+M])%q;
if(t<0)
t=t+q;
}
}
}
int main()
{
FILE* f1,*f2;
f1=fopen("strmatch.in","r");
f2=fopen("strmatch.out","w");
fscanf(f1,"%s %s",pat,txt);
if(strlen(pat)>strlen(txt))
{
fprintf(f2,"0\n");
return 0;
}
search(pat,txt,101);
fprintf(f2,"%d\n",count);
if(count>1000)
count=1000;
for(int i=0;i<count;i++)
fprintf(f2,"%d ",poz[i]);
fcloseall();
return 0;
}