Pagini recente » Cod sursa (job #1351525) | Cod sursa (job #2247835) | Cod sursa (job #1626087) | Cod sursa (job #785653) | Cod sursa (job #1889567)
#include<cstdio>
#include<cstring>
#define NMAX 2000002
#define LMAX 1000
using namespace std;
char P[NMAX], T[NMAX];
int L[NMAX], sol[LMAX], n, m, nrp, l;
int minim(int a, int b)
{
if(a < b) return a;
return b;
}
int main()
{
int i, k, val;
FILE *fin, *fout;
fin = fopen("strmatch.in","r");
fout = fopen("strmatch.out","w");
fscanf(fin,"%s",P);
fscanf(fin,"%s",T);
m = strlen(P);
n = strlen(T);
k = 0;
for(i=1; i<m; i++)
{
while(k > 0 && P[k] != P[i])
k = L[k-1];
if(P[k] == P[i])
k++;
L[i] = k;
}
k = 0;
for(i=0; i<n; i++)
{
while(k > 0 && P[k] != T[i])
k = L[k-1];
if(P[k] == T[i])
k++;
if(k == m)
{
nrp++;
if(l < LMAX)
sol[l++] = i-m+1;
}
}
val = minim(LMAX,l);
fprintf(fout,"%d\n",nrp);
for(i=0; i<val; i++)
fprintf(fout,"%d ",sol[i]);
fclose(fout);
return 0;
}