Pagini recente » Cod sursa (job #532992) | Cod sursa (job #702129) | Cod sursa (job #143653) | Cod sursa (job #2753313) | Cod sursa (job #731636)
Cod sursa(job #731636)
#include <cstdio>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
string a,b;
int p[2000001],poz[1024],n;
void read ()
{
string s;
ifstream in ("strmatch.in");
in>>s;
a=" "+s;
in>>s;
b=" "+s;
}
void solve ()
{
p[1]=0;
for(size_t i=2,q=0;i<a.size();++i)
{
for(;q&&a[q+1]!=a[i];q=p[q]);
if(a[q+1]==a[i])
++q;
p[i]=q;
}
for(size_t i=1,q=0;i<b.size();++i)
{
for(;q&&a[q+1]!=b[i];q=p[q]);
if(a[q+1]==b[i])
++q;
if(q+1==a.size())
{
q=p[a.size()-1];
++n;
if(n<=1000)
poz[n]=i-a.size()+1;
}
}
}
void out ()
{
freopen ("strmatch.out","w",stdout);
printf("%d\n",n);
for(int i=1;i<=min(1000,n);++i)
printf("%d ",poz[i]);
}
int main ()
{
read ();
solve ();
out ();
return 0;
}