Cod sursa(job #2425038)

Utilizator urweakurweak urweak Data 24 mai 2019 10:06:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb

#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n, m, nsol;
int pi[2000002];
char txt[2000002], pat[2000002];
int sol[1001];

void make_prefix()
{
	pi[1]=0;
	int k=0;
	for(int q=2; q<=m; ++q)
	{
			while(k>0 && pat[k+1]!=pat[q]) k=pi[k];
			if(pat[k+1]==pat[q]) ++k;
			pi[q]=k;
	}
}

int main()
{
	fin>>(pat+1);
	fin>>(txt+1);
	m=strlen(pat+1);
	n=strlen(txt+1);
	make_prefix();
	int q=0;
	for(int i=1; i<=n; ++i)
	{
			while(q>0 && txt[i]!=pat[q+1]) q=pi[q];
			if(txt[i]==pat[q+1]) ++q;
			if(q==m)
			{
					q=pi[m];
					++nsol;
					if(nsol<=1000) sol[nsol]=i-m;
			}
	}
	fout<<nsol<<"\n";
	for(int i=1; i<=min(nsol, 1000); ++i) fout<<sol[i]<<" ";
	fout<<"\n";
	return 0;
}