Cod sursa(job #700434)

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

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

inline void citire()
{
	ifstream fin("strmatch.in");
	fin.getline(a, 2000000);
	fin.getline(b, 2000000);
	fin.close();
}
inline void scriere()
{
	ofstream fout("strmatch.out");
	fout << aparitii.size() << '\n';
	for (int i = 0; i < 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;)
	{
		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)
	{
		if (a[i] == b[i + m])
		{
			if (a[i + 1] == 0)
			{
				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;
}