Pagini recente » Cod sursa (job #1123706) | Cod sursa (job #1217612) | Cod sursa (job #1860927) | Cod sursa (job #2747444) | Cod sursa (job #3041620)
#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++)
#define f first
#define s second
#define mod 111181111
using namespace std;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
ll q,n,m,i,j,k,l,p[2000001],t[2000001];char a[2000001],b[2000001];
int main()
{
//ios_base::sync_with_stdio(false);
//in.tie(nullptr),out.tie(nullptr);
in>>a>>b;
n=strlen(a),m=strlen(b);
for(i=1;i<n;i++)
{
while(a[i]!=a[j]&&j)
j=p[j-1];
if(a[i]==a[j])
p[i]=++j;
else p[i]=0;
}
//for(i=0;i<n;i++)cout<<p[i]<<' ';
j=0;
for(i=0;i<m;i++)
{
while(b[i]!=a[j]&&j)
j=p[j-1];
if(b[i]==a[j])
++j;
if(j==n)
{
t[k++]=i-n+1;
j=p[j-1];
}
}
out<<k<<'\n';
bminify(k,1000);
for(i=0;i<k;i++)out<<t[i]<<' ';
}