Pagini recente » Cod sursa (job #958131) | Cod sursa (job #1203920) | Cod sursa (job #798446) | Cod sursa (job #2497126) | Cod sursa (job #1203867)
#include<fstream>
#include<cstring>
using namespace std;
const int NMAX = 2000000+5;
void read();
void z_algorithm();
void print();
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,B,C;
int N,M,P;
int Z[NMAX*2];
int nrMatches;
int matches[1005];
int main()
{
read();
z_algorithm();
print();
return 0;
}
void read()
{
fin>>A;
fin>>B;
N=A.size();
M=B.size();
}
void z_algorithm()
{
int i,k,L,R;
C=A+' '+B;
P=N+1+M;
// Z[i] = lungimea celui mai lung prefix al lui C care incepe de pe C[i]
L=R=0;
for(i=1; i<P; i++)
{
if(i>R)
{
L=R=i;
while(C[R-L]==C[R] && R<P) R++;
R--;
Z[i]=R-L+1;
}
else
{
k=i-L;
if(Z[k]<R-i+1) Z[i]=Z[k];
else
{
L=i;
while(C[R-L]==C[R] && R<P) R++;
R--;
Z[i]=R-L+1;
}
}
if(Z[i]==N)
{
nrMatches++;
if(nrMatches<=1000) matches[nrMatches]=i-N-1;
}
}
}
void print()
{
int i;
fout<<nrMatches<<'\n';
for(i=1; i<=min(nrMatches,1000); i++)
fout<<matches[i]<<' ';
}