Cod sursa(job #1711666)

Utilizator MciprianMMciprianM MciprianM Data 31 mai 2016 21:35:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <string>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

static const int MAXN = 2000009;
int kmp_prefix[MAXN];
vector<int> pos;

bool matches(char a, char b)
{
	bool result = a == b || a == '*' || b == '*';
	return result;
}

void compute_prefix(const string& s)
{
	kmp_prefix[0] = 0;
	for (int i = 1; i < s.length(); i++)
	{
		bool found = false;
		for (int tmp = kmp_prefix[i - 1]; tmp != 0; tmp = kmp_prefix[tmp - 1])
		{
			if (matches(s[tmp], s[i]))
			{
				kmp_prefix[i] = tmp + 1;
				found = true;
				break;
			}
		}
		if (!found)
		{
			if (matches(s[i], s[0]))
			{
				kmp_prefix[i] = 1;
			}
			else
			{
				kmp_prefix[i] = 0;
			}
		}
	}
}

int count_matches(const string& t, const string& p)
{
	int match_count = 0;
	compute_prefix(p);
	int len = 0;
	for (int i = 0; i + p.size() <= t.size(); i += (len == 0 ? 1 : len - kmp_prefix[len - 1]))
	{
		for (int j = len = kmp_prefix[len - 1]; j < p.size(); j++)
		{
			if (matches(t[i + j], p[j]))
			{
				len++;
			}
			else
			{
				break;
			}
		}
		if (len == p.size())
		{
			match_count++;
			if (match_count <= 1000)
			{
				pos.push_back(i);
			}			
		}
	}
	return match_count;
}

int main()
{
	string t, p;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f >> p >> t;
	g << count_matches(t, p) << '\n';
	for (int i = 0; i < pos.size(); i++)
	{
		g << pos[i] << ' ';
	}
	g << endl;
	g.close();
	return 0;
}