Pagini recente » Cod sursa (job #2677212) | Cod sursa (job #1087172) | Cod sursa (job #1899990) | Cod sursa (job #1700296) | Cod sursa (job #2709333)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char t[40000100];
int z[40000100];
vector<int> sol;
void z_algoritm(int n,int m)
{
int st=0,dr=0,i;
z[0]=0;
for(int k=1;k<m;k++)
{
if(k>dr)
{
st=dr=k;
while(t[dr]==t[dr-st]&&dr<m)
dr++;
z[k]=dr-st;
dr--;
}
else
{
i=k-st;
if(k+z[i]<=dr)z[k]=z[i];
else
{
st=k;
while(t[dr]==t[dr-st]&&dr<m)
dr++;
z[k]=dr-st;
dr--;
}
}
if(z[k]==n)
{
sol.push_back(k-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));
fout<<sol.size()<<'\n';
for(int i=0;i<sol.size();i++)fout<<sol[i]<<" ";
}