Pagini recente » Cod sursa (job #144734) | Cod sursa (job #487448) | Cod sursa (job #2594585) | Cod sursa (job #1206675) | Cod sursa (job #1119153)
#include<stdio.h>
#include<string.h>
using namespace std;
FILE *in,*out;
//functii
void makePrefix();
//constante
const int sz=(int) 2e6+1;
//variabile
char sub[sz];
char str[sz];
int subLen,strLen;
int prefix[sz];
int answers[1001],answer;
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);
makePrefix();
int curentPrefix = 0;
for(int i=1 ; i<=strLen ; ++i)
{
while(curentPrefix && sub[curentPrefix+1]!=str[i])
curentPrefix=prefix[curentPrefix];
if(sub[curentPrefix+1] == str[i])
++curentPrefix;
if(curentPrefix==subLen)
{
if(++answer <= 1000)
answers[answer]=i-subLen+1;
curentPrefix=prefix[curentPrefix];
}
}
fprintf(out,"%d\n",answer);
for(int i=1 ; i<=answer ; ++i)
fprintf(out,"%d ",answers[i]);
fclose(in);
fclose(out);
return 0;
}
void makePrefix()
{
int curentPrefix = 0;
for(int i=2 ; i<=subLen ; ++i)
{
while(curentPrefix && sub[i]!=sub[curentPrefix+1])
curentPrefix = prefix[curentPrefix];
if(sub[curentPrefix+1] == sub[i])
++curentPrefix;
prefix[i]=curentPrefix;
}
}