Pagini recente » Cod sursa (job #2631144) | Cod sursa (job #383487) | Cod sursa (job #383569) | Cod sursa (job #1528488) | Cod sursa (job #2402674)
///Z
#include <fstream>
#include <algorithm>
#include <vector>
const int NMAX=4000000;
using namespace std;
int z[NMAX+5];
vector <int> v;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int main()
{
string a,b,s;
cin>>a>>b;
s=a;
s+="#";
s+=b;
int r=0,pozr=0;
for(int i=1; i<(int)s.size(); ++i)
{
if(i>r)
{
while(i+z[i]<(int)s.size() && s[i+z[i]]==s[z[i]])
z[i]++;
}
else
{
int leftover=min(z[i-pozr],r-i);
z[i]=leftover;
while(i+z[i]<(int)s.size() && s[i+z[i]]==s[z[i]])
z[i]++;
}
if(i+z[i]>r)
{
r=i+z[i];
pozr=i;
}
}
int cnt=0;
for(int i=1; i<(int)s.size(); ++i)
{
if(z[i]==(int)a.size())
{
cnt++;
if(cnt<=1000)
v.push_back(i-a.size()-1);
}
}
cout<<cnt<<'\n';
for( auto x: v)
cout<<x<<" ";
return 0;
}