Pagini recente » Cod sursa (job #3272741) | Cod sursa (job #2062002) | Cod sursa (job #98819) | Cod sursa (job #1621053) | Cod sursa (job #2042983)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char S[40000010],T[2000005];
int n,m,Z[40000010],nrrez;
void calcul(int m, char S[], int Z[])
{
int L,R,kp,beta;
Z[1]=0;
L=1;
R=1;
for (int 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]++;
if(Z[k]==n)
nrrez++;
}
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(Z[k]==n)
nrrez++;
}
if (k+Z[k]-1>R)
{
L=k;
R=k+Z[k]-1;
}
}
}
int main()
{
fin>>S+1;
n=strlen(S+1);
strcat(S+1,"$");
fin>>T;
strcat(S+1,T);
m=strlen(S+1);
calcul(m,S,Z);
fout<<nrrez<<"\n";
if(nrrez>1000)
m=n+2+1000;
for(int i=n;i<=m;i++)
{
if(Z[i]==n)
fout<<i-n-2<<" ";
}
fin.close();
fout.close();
return 0;
}