Pagini recente » Cod sursa (job #694100) | Cod sursa (job #610067) | Cod sursa (job #1785508) | Cod sursa (job #3243223) | Cod sursa (job #1124021)
#include<stdio.h>
#include<string.h>
using namespace std;
FILE *in,*out;
//functii
void make_prefix();
//constante
const int sz=(int)2e6+1;
//variabile
char str[sz],sub[sz];
int subLen,strLen;
int prefix[sz];
int answer,answers[1001];
int main(void)
{
in=fopen("strmatch.in","rt");
out=fopen("strmatch.out","wt");
fscanf(in,"%s",sub+1);
fscanf(in,"%s",str+1);
subLen=strlen(sub+1);
strLen=strlen(str+1);
make_prefix();
int curentPrefix=0;
for(int i=1 ; i<=strLen ; ++i)
{
while(curentPrefix && sub[curentPrefix+1]!=str[i])
curentPrefix=prefix[i];
if(sub[curentPrefix+1]==str[i])
++curentPrefix;
if(curentPrefix==subLen)
{
if(++answer<=1000)
answers[answer]=i-subLen;
curentPrefix=prefix[i];
}
}
fprintf(out,"%d\n",answer);
for(int i=1 ; i<=answer ; ++i)
fprintf(out,"%d ",answers[i]);
fclose(in);
fclose(out);
return 0;
}
void make_prefix()
{
int curentPrefix=0;
for(int i=2 ; i<=subLen ; ++i)
{
while(curentPrefix && sub[i]!=sub[curentPrefix+1])
curentPrefix = prefix[curentPrefix];
if(sub[i]==sub[curentPrefix+1])
++curentPrefix;
prefix[i]=curentPrefix;
}
}