Pagini recente » Cod sursa (job #1458959) | Cod sursa (job #345850) | Cod sursa (job #269452) | Cod sursa (job #1912903) | Cod sursa (job #2041573)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char P[2000002],T[2000002],S[4000004];
int Z[4000004];
int n,m,ck,beta;
int l,r,ind1,ind2;
int rez;
int main()
{
fi>>P;
fi>>T;
n=strlen(P);
strcpy(S,"*");
strcat(S,P);
strcat(S,"$");
strcat(S,T);
m=strlen(S+1);
Z[1]=n;
l=1;
r=1;
for (int k=2;k<=m;k++)
if (k>r)
{
ind1=1;
ind2=k;
while (S[ind1]==S[ind2])
{
ind1++;
ind2++;
}
Z[k]=ind1-1;
if (Z[k]!=0)
{
l=k;
r=ind2-1;
}
}
else
{
ck=k-(l-1);
beta=r-(k-1);
if (Z[ck]<beta)
Z[k]=Z[ck];
else
{
Z[k]=beta;
ind2=r+1;
ind1=ind2-(k-1);
while (S[ind1]==S[ind2])
{
Z[k]++;
ind1++;
ind2++;
}
if (k+Z[k]+1>=r)
{
l=k;
r=k+Z[k]+1;
}
}
}
// for (int i=1;i<=m;i++)
// fo<<S[i]<<" ";
// fo<<"\n";
// for (int i=1;i<=m;i++)
// fo<<Z[i]<<" ";
// fo<<"\n";
for (int i=n+2;i<=m;i++)
if (Z[i]==n)
rez++;
fo<<rez<<"\n";
for (int i=n+2;i<=m;i++)
if (Z[i]==n)
fo<<i-n-2<<" ";
fi.close();
fo.close();
return 0;
}