Cod sursa(job #1090784)

Utilizator SeekHunt1334Septimiu Bodica SeekHunt1334 Data 23 ianuarie 2014 08:20:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
#define DIM 2000005

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n, m, k, nrs;
string P, T;
vector<int> pi(DIM);
vector<int> sols(DIM);

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

int main()
{
	Read();
	Prefix();
	KMP();
	Write(); fout << '\n';

	fin.close();
	fout.close();
	return 0;
}

void Write()
{
    fout << nrs << '\n';
    for (int i = 0; i < nrs; ++i)
        fout << sols[i] << ' ';
}

void KMP()
{
	int q = 0;
	for (int i = 1; i <= n; ++i)
	{
		while ( q > 0 && P[q] != T[i-1] )
			q = pi[q];
		if ( P[q] == T[i-1] )
			q++;
		if ( q == m )
		{
		    nrs++;
            sols[nrs-1] = i - m;
			q = pi[q];
			if ( nrs == 1000 ) return;
		}
	}
}

void Prefix()
{
	m = P.length();
	n = T.length();

	for (int q = 2; q <= m; ++q)
	{
		while ( k > 0 && P[k] != P[q-1] )
			k = pi[k];
		if ( P[k] == P[q-1] )
			k++;
		pi[q] = k;
	}
}

void Read()
{
	fin >> P >> T;
}