Cod sursa(job #1575236)

Utilizator krityxAdrian Buzea krityx Data 21 ianuarie 2016 11:40:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	int i, j, plen, tlen;
	vector<int> v, matches;
	string pattern, text;
	ifstream f("strmatch.in");
	f >> pattern >> text;
	f.close();
	plen = pattern.length();
	tlen = text.length();
	v.resize(plen + 1);
	//preprocess
	i = j = 0;
	
	while (j < plen)
	{
		j++;
		if (pattern[j] == pattern[i])
		{
			v[j] = v[j - 1] + 1;
			i++;
		}
		else
		{
			i = 0;
			if (pattern[i] == pattern[j])
			{
				v[j]++;
				i++;
			}
		}
	}
	
	//match
	i = j = 0;
	while (i - j < tlen - plen + 1)
	{

		if (text[i] == pattern[j])
		{
			i++;
			j++;
			if (j == plen)
			{
				matches.push_back(i - j);
				int len = j;
				i = i - len + (len - v[len - 1]);
				j = 0;
			}
		}
		else
		{
			if (j == 0)
			{
				i++;
			}
			else
			{
				int len = j;
				i = i - len + (len - v[len - 1]);
				j = 0;
			}
		}
	}
	ofstream g("strmatch.out");
	g << matches.size() << "\n";
	for (vector<int>::iterator it = matches.begin(); it != matches.end(); it++)
	{
		g << *it << " ";
	}
	g.close();
	return 0;
}