Cod sursa(job #3243340)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 septembrie 2024 17:16:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int z[4000005];
void zfunc(string s)
{
	z[0]=0;
	int l=0;
	int r=0;
	for(int i=1;i<s.size();i++)
	{
		if(i<=r)
			z[i]=min(z[i-l],r-i);
		while(i+z[i]<s.size()&&s[z[i]]==s[i+z[i]])
			z[i]++;
		if(i+z[i]-1>r)
		{
			l=i;
			r=i+z[i]-1;
		}
	}	
}
int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0);
	fin>>a>>b;
	b=a+"#"+b;
	zfunc(b);
	int ans=0;
	vector<int> sol;
	for(int i=a.size();i<b.size();i++)
		if(z[i]==a.size())
		{
			ans++;
			if(sol.size()<1000)
				sol.push_back(i-a.size()-1);
		}
	fout<<ans<<'\n';
	for(int i:sol)
		fout<<i<<' ';
	fout<<'\n';
	return 0;
}