Cod sursa(job #2430760)

Utilizator gabriel.bjgGabriel b. gabriel.bjg Data 16 iunie 2019 12:49:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
//#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <fstream>

#define f(i,L,R) for (int i = (L); i < (R); ++i)
#define fe(i,L,R) for (int i = (L); i <= (R); ++i)

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const vector<unsigned> compute_lps(const string& pattern)
{
	vector<unsigned> lps(pattern.size());
	lps[0] = 0;
	unsigned i = 1, j = 0;
	while (i < pattern.size())
	{
		if (pattern[i] == pattern[j])
		{
			j++;
			lps[i++] = j;
		}
		else
		{
			if (j == 0)
			{
				lps[i] = 0;
				i++;
			}
			else
				j = lps[j - 1];
		}
	}

	return lps;
}



int main()
{
	compute_lps("ABCDEABCF");

	string pattern, text;
	fin >> pattern >> text;

	auto lps = compute_lps(pattern);

	unsigned i = 0, j = 0, nr_of_matches = 0;
	vector<unsigned> matched_pos;
	while (i < text.length())
	{
		if (text[i] == pattern[j])
		{
			i++;
			j++;
		}

		if (j == pattern.length())
		{
			if(nr_of_matches < 1000)
				matched_pos.push_back(i - j);
			nr_of_matches++;
			j = lps[j - 1];
		}
		else if (i < text.length() && text[i] != pattern[j])
		{
			if (j == 0)
				i++;
			else
				j = lps[j - 1];
		}
	}

	fout << nr_of_matches << "\n";
	for (auto& pos : matched_pos)
		fout << pos << " ";
}