Pagini recente » Cod sursa (job #2803055) | Cod sursa (job #849560) | Cod sursa (job #1339908) | Cod sursa (job #783299) | Cod sursa (job #2465420)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.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=2;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();++i)
{
if(z[i]==c.length())
mys++;
}
g<<mys<<"\n";
for(long long unsigned i=m+1;i<=s.length();++i)
{
if(z[i]==c.length())
g<<i-m-1<<" ";
}
}
int main()
{
f>>s1>>s2;
findin(s1,s2);
return 0;
}