Cod sursa(job #1592373)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 7 februarie 2016 15:50:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
// KMPforMicrosoft.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <vector>
#include <string>
#include <iostream>

#define N 1000

using namespace std;

vector<int> getKmpMachine(const string & str) {
	vector<int> kmp(str.size() + 1, 0);
	int state = 0;

	for (size_t i = 1; i < str.length(); ++i) {
		while (state > 0 && str[state] != str[i]) {
			state = kmp[state];
		}
		if (str[state] == str[i])
			++state;
		kmp[i + 1] = state;
	}

	return kmp;
}

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

int main()
{
	string small, large;
	
	fin >> small;
	fin >> large;

	vector<int> kmpMachine = getKmpMachine(small);
	vector<int> result;

	int count = 0;
	size_t state = 0;
	for (size_t i = 0; i < large.length(); ++i) {
		while (state > 0 && large[i] != small[state]) {
			state = kmpMachine[state];
		}
		if (small[state] == large[i])
			++state;

		if (state == small.length()) {
			++count;
			state = kmpMachine[state];

			if (count <= N) {
				result.push_back(i - small.length() + 1);
			}
		}
	}

	fout << count << "\n";
	for (size_t i = 0; i < result.size(); ++i) {
		fout << result[i] << ' ';
	}

    return 0;
}