Cod sursa(job #1701751)

Utilizator cpitting_llamasRotaru Tanase Gherghina cpitting_llamas Data 13 mai 2016 23:45:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <string>
#include <limits>
#include <vector>
#include <bitset>
#include <utility>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define MOD 10001 // daca e nevoie de mod
#define oo 2000000000
#define ooLL (1LL<<60)
#define LSB(x) (x&(-x)) // least significat bit of
#define eps 0.00001

typedef long long ull;
typedef long double ld;

std::vector<int> compute_pattern_kmp(const std::string& pattern)
{
	std::vector<int> pp(pattern.size(), 0);

	uint j = 0;
    for (uint i = 1; i <= pattern.size(); ++i)
    {
		while(0 != j && pattern[i] != pattern[j]) {
			j = pp[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			j++;
		}
		pp[i] = j;
    }
	return pp;
}

std::vector<int> positions_matched_kmp(const std::string& pattern, const std::string& text)
{
	std::vector<int> pos;
	uint j = 0;
	const std::vector<int>& pp = compute_pattern_kmp(pattern);

	for (uint i = 0; i < text.size(); ++i)
	{
		while(0 != j && pattern[j] != text[i]) {
			j = pp[j - 1];
		}
		if (pattern[j] == text[i]) {
			j++;
		}
		if (j == pattern.size()) {
			j = pp[pattern.size() - 1];
			pos.push_back(i - pattern.size() + 1);
		}
	}
	return pos;
}


int main()
{
	std::ifstream cin("strmatch.in");
	std::ofstream cout("strmatch.out");

	size_t N = 1000;
	std::string pattern;
	std::string text;

	cin >> pattern >> text;

	std::vector<int> match_positions = positions_matched_kmp(pattern, text);

	cout << match_positions.size() << "\n";
	for (size_t i = 0; i < std::min(match_positions.size() , N); ++i)
		cout << match_positions[i] << " ";

	cin.close();
	cout.close();
	return 0;
}