Cod sursa(job #1399094)

Utilizator alexb97Alexandru Buhai alexb97 Data 24 martie 2015 16:07:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#define DIM 2000000
using namespace std;

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

int n, m;
string cuv, sir;
int cnt;
int p[DIM], pos[1024];

void Prefix();
void KMP();

int main()
{
	getline(is, cuv);
	getline(is, sir);
	m = cuv.length();
	n = sir.length();
	KMP();
	os << cnt << '\n';
	for ( int i = 0; i < cnt; ++i )
        os << pos[i] << ' ';
	is.close();
	os.close();
	return 0;
}


void Prefix()
{
	int k = 0;
	for (int i = 1; i < m; i++)
	{
		while ( k > 0 && cuv[k] != cuv[i] )
			k = p[k - 1];

		if ( cuv[k] == cuv[i] ) 
			k++;
        p[i] = k; 
	}
}

void KMP()
{
	Prefix();
	int k = 0;
	for(int i = 0 ; i <= n; ++i)
	{
		while(k > 0 && cuv[k] != sir[i])
			k = p[k-1];
			
		if(cuv[k] == sir[i]) 
			k++;
		
		if(k == m)
		{
			if(cnt < 1000)
				pos[cnt] = i - m + 1;
			cnt++;
		}
	}
}