Pagini recente » Cod sursa (job #1031284) | Cod sursa (job #2184969) | Cod sursa (job #165145) | Cod sursa (job #1040065) | Cod sursa (job #1131504)
#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 strLen,subLen;
int answer,answers[1001];
int prefix[sz];
int main(void)
{
in=fopen("strmatch.in","rt");
out=fopen("strmatch.out","wt");
fscanf(in,"%s",sub+1);
fscanf(in,"%s",str+1);
strLen = strlen(str+1);
subLen = strlen(sub+1);
make_prefix();
int curentPrefix=0;
for(int i=1 ; i<=strLen ; ++i)
{
while(curentPrefix && str[i]!=sub[curentPrefix+1])
curentPrefix = prefix[curentPrefix];
if(sub[curentPrefix+1] == str[i])
++curentPrefix;
if(curentPrefix == subLen)
if(++answer<=1000)
{
answers[answer] = i-subLen;
curentPrefix = prefix[curentPrefix];
}
}
fprintf(out, "%d\n",answer);
if(answer<=1000)
for(int i=1 ; i<=answer ; ++i)
fprintf(out, "%d ",answers[i]);
else
for(int i=1 ; i<=1000 ; ++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;
}
}