Cod sursa(job #700453)

Utilizator blustudioPaul Herman blustudio Data 1 martie 2012 10:25:20
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

char a[2000005], b[2000005];
int t[2000005];
vector<int> aparitii;

inline void citire()
{
	ifstream fin("strmatch.in");
	fin.getline(a, 2000005);
	fin.getline(b, 2000005);
	fin.close();
}
inline void scriere()
{
	ofstream fout("strmatch.out");
	fout << aparitii.size() << '\n';
	for (int i = 0; i < min(1000, aparitii.size()); i++)
		fout << aparitii[i] << ' ';
	fout.close();
}
inline void prefix()
{
	int candidat = 0;
	t[0] = -1;
	t[1] = 0;
	for (int i = 2; (a[i] != 0) && (a[i] != '\n');)
	{
		if (a[i - 1] == a[candidat])
		{
			candidat++;
			t[i] = candidat;
			i++;
		}
		else if (candidat > 0)
			candidat = t[candidat];
		else
		{
			t[i] = 0;
			i++;
		}
	}
}
inline void kmp()
{
	int i = 0; //Pozitia in a
	int m = 0; //Pozitia in b
	while ((b[i + m] != 0) && (aparitii.size() < 1001))
	{
		if (a[i] == b[i + m])
		{
			if ((a[i + 1] == 0) || (a[i + 1] == '\n'))
			{
				aparitii.push_back(m);
				m = m + i - t[i];
				if (t[i] > -1)
					i = t[i];
				else
					i = 0;
			}
			else
				i++;
		}
		else
		{
			m = m + i - t[i];
			if (t[i] > -1)
				i = t[i];
			else
				i = 0;
		}
	}
}
int main()
{
	citire();
	prefix();
	kmp();
	scriere();
	return 0;
}