Pagini recente » Cod sursa (job #3221743) | Cod sursa (job #3152256) | Cod sursa (job #868961) | Cod sursa (job #2783976) | Cod sursa (job #2970927)
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
using namespace std;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
ll i,j,k,l,s[2000001],t;string p,q;vector<int>e;
int main()
{
in>>p>>q;
for(i=1;i<p.size();i++)
{
if(p[i]==p[j])
++j;
else
{
do{
j=s[j];
}while(j&&p[i]!=p[j]);
if(p[i]==p[j])
++j;
}
s[i]=j;
//cout<<s[i]<<' ';
}
j=0;
for(i=0;i<q.size();i++)
{
if(q[i]==p[j])
++j;
else{
do{
j=s[j];
}while(j&&p[i]!=p[j]);
if(q[i]==p[j])
++j;
}
if(j==p.size())
{
if(++t<1001)
e.push_back(i-j+1);
j=s[p.size()-1];
}
}
cout<<e.size()<<'\n';
for(i=0;i<bmin(e.size(),1000);i++)
cout<<e[i]<<' ';
}