Cod sursa(job #1483736)

Utilizator tain1234andrei laur tain1234 Data 9 septembrie 2015 20:29:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <vector>
#include <string>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
vector<int> f;
int nr = 0;
ofstream g("strmatch.out");
string target, pattern;
int a[1001];
void pre()
{
	int m = pattern.length(), k;
	f[0] = -1;
	for (int i = 1; i <=m; i++)
	{
		k = f[i - 1];
		while (k >= 0)
		{
			if (pattern[k] == pattern[i - 1])
				break;
			else
				k = f[k];
		}
		f[i] = k + 1;
	}
}
void KMP()
{
	int m = pattern.length();
	int n = target.length();
	f.resize(m+1);
	pre();
	int i = 0;
	int k = 0;
	while (i < n)
	{
		if (k == -1)
		{
			++i;
			k = 0;
		}
		else if (target[i] == pattern[k])
		{
			++i;
			++k;
			if (k == m){
				if (nr < 1000)a[nr] = i - m;
				++nr;
				k = f[k];
			}
		}
		else
			k = f[k];
	}
	if (nr < 1000)a[nr] = -1; else a[1000] = -1;
}
int main()
{
	in >> pattern;
	in >> target;
	KMP();
	g << nr << "\n";
	for (int i = 0; i < 1000; ++i){
		if (a[i] == -1)break;
		g << a[i] << " ";
	}
	return 0;
}