Pagini recente » Cod sursa (job #2634796) | Cod sursa (job #1674669) | Cod sursa (job #1557382) | Cod sursa (job #16672) | Cod sursa (job #2465460)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f ("zet.in");
ofstream g ("zet.out");
long long unsigned z[4000004];
long long unsigned r,l;
string s1, s2;
void findin(string c, string st)
{
string s=c+"*"+st;
long long unsigned t;
z[1]=0;
long long unsigned n=s.length();
long long unsigned k=2;
for(k=1;k<n;++k)
{
if(k>=r)
{
l=r=k;
while(r<n && s[r-l] == s[r])
r++;
z[k]=r-l;
r--;
} else {
t=k-l;
if(z[t] < r-k+1)
z[k]=z[t];
else {
l=k;
while(s[r] == s[r-l] && r<n)
r++;
z[k]=r-l;
r=r-1;
}
}
}
long long unsigned m=c.size();
long long unsigned mys=0;
for(long long unsigned i=m+1;i<=s.length()+3;++i)
{
// g<<z[i]<<" ";
if(z[i]==c.length())
mys++;
}
// g<<"\n";
g<<mys<<"\n";
int o=0;
for(long long unsigned i=m+1;i<=s.length();++i)
{
if(z[i]==c.length())
{
o++;
g<<i-m-1<<" ";
}
if(o>999)
return;
}
}
int main()
{
f>>s1>>s2;
findin(s1,s2);
return 0;
}