Cod sursa(job #1758675)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 17 septembrie 2016 17:25:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

string a, b;
int r = 0;
vector <int> rez;
int pi[2000010];

void pref();

int main()
{
	ifstream in("strmatch.in");
	ofstream out("strmatch.out");
	in >> a >> b;
	pref();
	int k = 0;
	for (int i = 0; i < b.size(); i++) {
		while (a[k + 1] != b[i] && k > 0)
			k = pi[k];

		if (a[k + 1] == b[i]) {
			k++;
			if (k == a.size() - 1) {
				k = pi[k];
				r++;
				rez.push_back(i - a.size() + 2);
			}
		}
	}
	out << r << '\n';
	for (int i = 0; i < 1000 && i < rez.size(); i++)
		out << rez[i] << ' ';
	return 0;
}

void pref()
{
	a = "$" + a;
	int k = 0;
	for (int i = 2; i < a.size(); i++) {
		while (k != 0 && a[i] != a[k + 1])
			k = pi[k];

		if (a[i] == a[k + 1])
			pi[i] = ++k;
	}
}