Cod sursa(job #1399010)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 24 martie 2015 15:12:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <string>
using namespace std;

ifstream is("strmatch.in");
ofstream os("strmatch.out");

string P, T;
int n, m;
int cnt;
int poz[2000001];
int ps[2000001];

void Read();
void Prefix();
void KMP();

int main()
{
	Read();
	Prefix();
	KMP();
	os << cnt << '\n';
	for ( int i = 0; i < cnt; ++i )
		os << poz[i] << ' ';
	is.close();
	os.close();
	return 0;
}

void Read()
{
	getline(is, P);
	getline(is, T);
	m = P.length();
	n = T.length();
}

void Prefix()
{
	int k = 0;
	for ( int i = 1; i <= m; ++i )
	{
		while ( k > 0 && P[k] != P[i] )
			k = ps[k - 1];
			
		if ( P[k] == P[i] )
			++k;
			
		ps[i] = k;
	}
}

void KMP()
{
	int k = 0;
	for ( int i = 0; i <= n; ++i )
	{
		while ( k > 0 && P[k] != T[i] )
			k = ps[k - 1];
			
		if ( P[k] == T[i] )
			++k;
			
		if ( k == m )
			poz[cnt++] = i - m + 1;
	}
}