Cod sursa(job #1232292)

Utilizator daniel.amarieiDaniel Amariei daniel.amariei Data 22 septembrie 2014 17:19:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <iostream>
#define MAX_MATCHES 1000
#define MAX_LENGTH 2000001
#define MIN(a, b) ((a) < (b) ? (a) : (b))
using namespace std;

int POSITIONS[MAX_MATCHES];
int PREFIX[MAX_LENGTH];
int n_matches;

void compute_prefix(string & P)
{
	int m = P.length();
	PREFIX[1] = 0;
	
	for (int i = 1; i < m; ++i)
	{
		int k = PREFIX[i];
		while (k > 0 && P[k] != P[i])
			k = PREFIX[k];
		
		if (P[k] == P[i]) 
			k = k + 1;
		
		PREFIX[i+1] = k;	
	}
}

void KMP(string & P, string & T)
{
	compute_prefix(P);

	int m = P.length();
	int n = T.length();
		
	int k = 0;	
	for (int i = 0; i < n; ++i)
	{
		while (k > 0 && P[k] != T[i])
			k = PREFIX[k];

		if (P[k] == T[i])
			k = k + 1;
			
		if (k == m)	
		{
			if (n_matches < MAX_MATCHES)
				POSITIONS[n_matches] = i - m + 1;
				
			++n_matches;
			
			k = PREFIX[k];
		}
	}
}

int main()
{
	ifstream ifs("strmatch.in");
	ofstream ofs("strmatch.out");
	
	string A, B; 
	ifs >> A >> B;
	
	KMP(A, B);
	
	ofs << n_matches << "\n";
	for (int i = 0; i < MIN(n_matches, MAX_MATCHES); ++i)
		ofs << POSITIONS[i] << " ";

	return 0;
}