Pagini recente » Cod sursa (job #698790) | Cod sursa (job #3122128) | Cod sursa (job #2866303) | Cod sursa (job #345600) | Cod sursa (job #2709350)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char t[40000100];
int z[40000100];
void z_algoritm(int n,int m)
{
int st=0,dr=0,i,nr=0;
z[0]=0;
for(int k=1;k<m;k++)
{
if(k>dr)
{
st=dr=k;
while(dr<m&&t[dr]==t[dr-st])
dr++;
z[k]=dr-st;
dr--;
}
else
{
i=k-st;
if(k+z[i]<=dr)z[k]=z[i];
else
{
st=k;
while(dr<m&&t[dr]==t[dr-st])
dr++;
z[k]=dr-st;
dr--;
}
}
if(z[k]==n)nr++;
}
fout<<nr<<'\n';
for(int i=1;i<m;i++)
{
if(z[i]==n)fout<<i-n-1<<" ";
}
}
int main()
{
fin.getline(t,20000005);
int n=strlen(t);
t[n]='$';
fin.getline(t+n+1,2000005);
z_algoritm(n,strlen(t));
}