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