Pagini recente » Cod sursa (job #2048205) | Cod sursa (job #2279817) | Cod sursa (job #2551244) | Cod sursa (job #383950) | Cod sursa (job #2051697)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char S[2000005],T[2000005];
int n,m,Z[2000005],v[2000005],t;
void calcul(int m, char S[], int Z[])
{
int L,R,k,kp,beta;
Z[1]=0;
L=R=1;
for (k=2;k<=m;k++)
if (S[k]!=S[1])
Z[k]=0;
else
if (k>R)
{
Z[k]=1;
while (S[k+Z[k]]==S[1+Z[k]])
Z[k]++;
L=k;
R=k+Z[k]-1;
}
else
{
kp=k-(L-1);
beta=R-(k-1);
Z[k]=min(Z[kp],beta);
while (S[k+Z[k]]==S[1+Z[k]])
Z[k]++;
if(k+Z[k]-1>R)
{
L=k;
R=k+Z[k]-1;
}
}
}
int main()
{
f>>S+1;
n=strlen(S+1);
strcat(S+1,"$");
f>>T;
strcat(S+1,T);
m=strlen(S+1);
calcul(m,S,Z);
for (int i=1;i<=m;i++)
if(Z[i]==n)
{
t++;
v[t]=i;
}
g<<t<<endl;
if(t<1000)
for(int i=1;i<=t;i++)
g<<v[i]-n-2<<' ';
else
for(int i=1;i<=1000;i++)
g<<v[i]-n-2<<' ';
return 0;
}