Pagini recente » Cod sursa (job #1972073) | Cod sursa (job #3294944) | Cod sursa (job #355641) | Cod sursa (job #1842950) | Cod sursa (job #1826928)
#include <fstream>
#include <cstring>
#define LIM 2000001
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char T[LIM],P[LIM],S[LIM];
int i,r,s,p,k;
int A[LIM],REZ[LIM];
int main()
{
fi.getline(P,LIM);
fi.getline(T,LIM);
strcpy(S,P);
strcat(S,"*");
strcat(S,T);
s=strlen(S);
p=strlen(P);
A[0]=0;
for(i=1;i<s;i++)
{
r=A[i-1];
while(r>0)
{
if(S[i]==S[r])
break;
else
r=A[r-1];
}
if(S[i]==S[r])
A[i]=r+1;
else
A[i]=r;
}
for(i=0;i<s;i++)
if(A[i] == p)
REZ[++k]=i-2*p;
fo<<k<<"\n";
for(i=1;i<=min(1000,k);i++)
fo<<REZ[i]<<" ";
fi.close();
fo.close();
return 0;
}