Cod sursa(job #2419136)

Utilizator potirasUAIC Borcan Andreea potiras Data 7 mai 2019 18:22:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_p(x) cerr<<#x": "<<x.first<<","<<x.second<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define DMAX 2000020
#define NMAX 137
#define MMAX 1

using namespace std;

int n, k,  y,m,i,j;
unsigned long long x,h[DMAX],has[DMAX];
short ans[DMAX];
string a,b;

int main()
{
ifstream cin ("strmatch.in");
ofstream cout("strmatch.out");
	ios_base::sync_with_stdio(false);
	cin>>a>>b;
	h[0]=1;
	for(i=1;i<DMAX-15;i++)
	{
		h[i]=h[i-1]*NMAX;
		//dbg(h[i]);
	}
	n=a.size();
	int cn=n;
	n--;
	//dbg(x);
	for (int i = 0; i < cn; ++i)
	{
		x+=((unsigned long long)a[i]*h[n]);
		//dbg(x);
		has[0]+=(unsigned long long)b[i]*h[n];
		n--;
		//dbg(n);
	}
	j=0;
	int l=1;
	for (int i = cn; i < b.size(); ++i)
	{
		has[l]=(has[l-1] - ((unsigned long long) b[j])*h[cn-1])*NMAX+(unsigned long long)b[i];
		//dbg(b[j]*h[cn]);
		//dbg(has[l]);
		l++;
		j++;
	}
	n=0;
	//dbg(x);
	for(i=0;i<l;i++)
	{
		//dbg(i);
		//dbg(has[i]);
		if(has[i]==x )
		{
			ans[n]=i;
			n++;
		}
	}

	cout<<n<<'\n';
	for (int i = 0; i < min(n,1000); ++i)
	{
		cout<<ans[i]<<' ';
	}
}