Pagini recente » Cod sursa (job #776634) | Cod sursa (job #1293215) | Cod sursa (job #1398029) | Cod sursa (job #2752662) | Cod sursa (job #2709329)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005],b[2000005];
short int t[4000002];
int z[4000002];
vector<int> sol;
void z_algoritm(int n,int m)
{
for(int i=0;i<n;i++)
{
t[i]=a[i];
}
t[n]=-1;
for(int i=0;i<m;i++)
{
t[n+i+1]=b[i];
}
m=n+m+1;
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(a,2000005);
fin.getline(b,2000005);
z_algoritm(strlen(a),strlen(b));
fout<<sol.size()<<'\n';
for(int i=0;i<sol.size();i++)fout<<sol[i]<<" ";
}