Pagini recente » Cod sursa (job #1898921) | Cod sursa (job #2357351) | Cod sursa (job #486674) | Cod sursa (job #1209148) | Cod sursa (job #2870624)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,S;
int z[4000005];
vector<int> sol;
void z_function()
{
z[0]=0;
int l=0,r=0;
for(int i=1;i<S.size();i++)
{
bool ok=0;
if(i==6)
ok=1;
if(i<=r)
z[i]=min(z[i-l],r-i+1);
while(i+z[i]<S.size()&&S[z[i]]==S[i+z[i]])
z[i]++;
if(i+z[i]-1>r)
{
r=i+z[i]-1;
l=i;
}
}
}
int main()
{
fin>>A>>S;
S=A+"#"+S;
z_function();
/*for(int i=0;i<S.size();i++)
fout<<z[i]<<' ';*/
for(int i=0;i<S.size();i++)
if(z[i]==A.size())
{
int index=i-A.size();
sol.push_back(index-1);
}
fout<<sol.size()<<'\n';
for(int i=0;i<min(1000,(int)sol.size());i++)
fout<<sol[i]<<' ';
return 0;
}