Cod sursa(job #348483)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 15 septembrie 2009 21:10:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>

using namespace std;

#define fin  "strmatch.in"
#define fout "strmatch.out"

#define NMAX 2000100

char a[NMAX], b[NMAX];
int pi[NMAX];

void prefix(char a[], int pi[])
{
	int i, pos;

	pi[ 1 ] = 0;
	pos = 0;

	for ( i = 2; a[i]; ++i )
	{
		while ( pos > 0 && a[pos+1] != a[i] )
			pos = pi[pos];
		if ( a[pos+1] == a[i] )
			++pos;
		pi[i] = pos;
	}
}

int kmp(char model[], char str[], int pif[])
{
	int i, pos, ret = 0;

	pos = 0;
	for ( i = 1; str[i]; ++i )
	{
		while ( pos > 0 && model[ pos + 1 ] != str[i] )
			pos = pif[pos];
		if ( model[ pos + 1 ] == str[i] )
			++pos;
		if ( model[ pos + 1 ] == 0 )
			str[i - pos + 1] = 1, pos = pi[pos], ++ret;
	}

	return ret;
}

int main()
{
	int cnt = 0;

	ifstream f1(fin);
	ofstream f2(fout);

	f1 >> a+1 >> b+1;

	prefix(a,pi);

	f2 << kmp(a,b,pi) << endl;
	for ( int i = 1; b[i] && cnt < 1000; ++i )
		if ( b[i] == 1 )
			f2 << i - 1 << " ", ++cnt;

	return 0;
}