Pagini recente » Cod sursa (job #1523517) | Cod sursa (job #2472595) | Cod sursa (job #1465131) | Cod sursa (job #158424) | Cod sursa (job #2515549)
#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;
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;
for(i=2; i<=p; ++i)
if(patt[i] == patt[lps[i-1]+1])
lps[i] = lps[i-1]+1;
else
{
j = lps[i-1]+1;
while(j>0 and patt[i] != patt[j])
j = lps[j-1]+1;
if(j == 0)
lps[i] = 0;
else
lps[i] = j;
}
i = 1; j = 1;
while(i<=t and nrap<1000)
{
while(i<=t and j<=p and patt[j] == txt[i])
{ ++i; ++j;}
if(j > p)
{
ap[++nrap] = i-p-1;
j = lps[p]+1;
continue;
}
if(i>t)
break;
k = lps[j-1]+1;
while(k>0 and patt[k]!=txt[i])
k = lps[k-1]+1;
if(k>0)
j = k;
else
{
j = 1;
++i;
}
}
fprintf(fout, "%d\n", nrap);
for(i=1; i<=nrap; ++i)
fprintf(fout, "%d ", ap[i]);
fclose(fin);
fclose(fout);
return 0;
}