Pagini recente » Cod sursa (job #755260) | Sandbox (cutiuţa cu năsip) | Cod sursa (job #812358) | Cod sursa (job #223737) | Cod sursa (job #1216498)
#include <fstream>
#include <cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char Nb1[2*NMAX],Nb2[2*NMAX],Nb3[2*NMAX];
int Solution[1005];
long long Result;
int Z[2*NMAX];
int N,M,L,R;
void Read()
{
f.getline(Nb2,NMAX);
f.getline(Nb1,NMAX);
N=strlen(Nb1);
M=strlen(Nb2);
for(int i=M;i<=M+N-1;i++)
Nb2[i]=Nb1[i-M];
for(int i=1;i<=M+N;i++)
Nb3[i]=Nb2[i-1];
}
int newPosition(int k,int start)
{
int result=0;
while(Nb3[start]==Nb3[k] && k<=N+M)
{
result++;
start++;
k++;
}
return result;
}
void precalcZ()
{
int i;
Z[1]=M+N;
for(int k=2;k<=M+N;k++)
{
if(k>R)
{
Z[k]=newPosition(k,1);
L=k;R=k+Z[k]-1;
}
else
{
int aux=k-L+1;
if(Z[aux]<R-k+1)
Z[k]=Z[aux];
else
{
int poz=R+1+newPosition(R+1,R-k+2);
Z[k]=poz-k;R=poz-1;L=k;
}
}
}
}
void Browse()
{
int i;
for(i=M+1;i<=N+1;i++)
if(Z[i]>=M)
{
Result++;
if(Solution[0]<1000)
Solution[++Solution[0]]=i-M-1;
}
g<<Result<<"\n";
for(int i=1;i<=Solution[0];i++)
g<<Solution[i]<<" ";
}
int main()
{
Read();
precalcZ();
Browse();
return 0;
}