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