Cod sursa(job #852360)

Utilizator SteveStefan Eniceicu Steve Data 11 ianuarie 2013 04:53:08
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int N, M, T[2000011];
string A, B;
vector <int> v;

void Precalc ()
{
	int cnd = 0, pos = 2;
	T[0] = -1;
	T[1] = 0;
	while (pos < M)
	{
		if (B[pos - 1] == B[cnd]) T[pos++] = ++cnd;
		else if (cnd) cnd = T[cnd];
		else T[pos++] = 0;
	}
}

void KMP ()
{
	int m = 0, i = 0;
	while (m + i < N)
	{
		if (B[i] == A[m + i])
		{
			if (i == M - 2) v.push_back (m);
			i++;
		}
		else
		{
			m += i - T[i];
			i = (T[i] > -1 ? T[i] : 0);
		}
	}
}

int main ()
{
	ifstream fin ("strmatch.in");
	ofstream fout ("strmatch.out");
	fin >> A >> B;
	N = A.size ();
	B.push_back ('$');
	M = B.size ();
	fin.close ();
	Precalc ();
	KMP ();
	N = v.size ();
	fout << N << "\n";
	for (int i = 0; i < min (N, 1000); i++)
		fout << v[i] << " ";
	fout.close ();
	return 0;
}