Pagini recente » Cod sursa (job #2004395) | Cod sursa (job #1711992) | Cod sursa (job #2191947) | Cod sursa (job #2370537) | Cod sursa (job #2515748)
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int p,t,i,j,lps[2000005],nrap,ap[1001],k,lg;
char patt[2000005],txt[2000005];
int main()
{
fgets(patt+1, 2000005, fin);
fgets(txt+1, 2000005, fin);
patt[0] = txt[0] = '.';
p = strlen(patt) - 2;
t = strlen(txt) - 2;
lps[0] = -1;lps[1]=0;
lg=0;
//lg indica cate caractere aflate la inceputul cuvantului sunt identice cu caracterele aflate pana la i-1(inclusiv)
for(i=2; i<=p; ++i){
while(lg>0 and patt[i]!=patt[lg+1])
lg=lps[lg];
if(patt[i]==patt[lg+1])
lg++;
lps[i]=lg;
}
i = 1; j = 1;lg=0;
//lg reprezinta cate caractere de la inceputul lui patt sunt egale cu cele aflate in txt, pana la i-1(inclusiv)
while(i<=t and nrap<1000)
{
while(lg>0 and txt[i]!=patt[lg+1])
lg=lps[lg];
if(txt[i]==patt[lg+1])
lg++;
if(lg==p)
{
ap[++nrap]=i-p;
lg=lps[p];
}
i++;
}
fprintf(fout, "%d\n", nrap);
for(i=1; i<=nrap; ++i)
fprintf(fout, "%d ", ap[i]);
fclose(fin);
fclose(fout);
return 0;
}