Cod sursa(job #841600)

Utilizator lucian666Vasilut Lucian lucian666 Data 24 decembrie 2012 14:57:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb



//Vasilut
//Z-Algorithm

#include<fstream>
#include<string>
#include<vector>

#define NN 2000005
using namespace std;
ofstream out("strmatch.out");

string a,b,s;

int n;

vector<int>sol;
int z[ 2*NN ];

void read();
void Z_A();
void write_sol();

int main()
{
	read();
	Z_A();
	write_sol();
	return 0;
}

void read()
{
	ifstream in("strmatch.in");
	in >> a >> b;
	
	s = a + '?' + b;
	
	n = s.size();
}

void Z_A()
{

	//z[i] - cel mai lung substring care incepe din s[i] si este prefix al lui S
	int st,dr ,i ;
	st = dr = 0;
	for (  i =1 ; i<n; i++)
	{
		if ( i > dr ) // nu exista nici un prefix al lui S care sa inceapa inainte de i si sa se termine in sau dupa i
		{
			st = i;
			dr = i;
			while ( dr < n && s[ dr - st ] == s[ dr ] ) 
				dr++;
			z[i] = dr - st;
			dr -- ;
		}
		
		else
		{
			int k = i - st;
			
			if ( z[k] < dr - i + 1 )
				z[i] = z[k];
			else
			{
				st = i;
				while ( dr < n && s[ dr - st ] == s[ dr ] )
					dr++;
				z[i] = dr - st;
				dr -- ;
			}
		}
		
		if ( z[i] == a.size() )
		{
			int val = i - z[i];
			--val;
			sol.push_back(val);
		}
			//sol.push_back( i - z[i] - 1 );
			//out << i - z[i] - 1 <<" ";
		
	}
			
			

}




void write_sol()
{
	out << sol.size() <<'\n';
	int how = 0;
	for(int i=0;i<sol.size() && how < 1000; ++i )
	{
		++how;
			out << sol[i] <<" ";
	}
	

}