Cod sursa(job #1168287)

Utilizator federerUAIC-Padurariu-Cristian federer Data 7 aprilie 2014 21:03:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
#define Nmax 2000010
using namespace std;

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

string A, B;
vector<int>sol;
int p[Nmax]={-1, 0}, i, j, c;
void prefix()
{
	i=0;
	for(j=1;j<A.size();++j)
	{
		while(A[i]==A[j] && j<A.size())
		{
			i++,j++;
			p[j]=p[j-1]+1;
		}
		i=0;
		if(A[i]==A[j])
		{
			i++;
			p[j+1]=1;
		}
	}
}
void solve()
{
	int k=0;
	c=0;
	for(i=0;i<B.size();++i)
	{
		while(k>0 && A[k]!=B[i])
			k=p[k];
		if(A[k]==B[i])k++;
		if(k==A.size())
		{
			c++;
			if(c<=1000)
				sol.push_back(i-A.size()+1);
		}
	}

}
int main()
{
	fin>>A>>B;
	prefix();
	solve();
	fout<<c<<'\n';
	for(i=0;i<min(c,1000);++i)
		fout<<sol[i]<<' ';

	return 0;
}