Cod sursa(job #1725706)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 6 iulie 2016 11:12:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

void calc();

int main()
{
	ifstream in("strmatch.in");
	in >> a >> b;
	a = "." + a;
	calc();
	int q = 0;
	for (int i = 0; i < b.size(); i++) {
		while (q && a[q + 1] != b[i])
			q = pi[q];
		if (a[q + 1] == b[i])
			q++;
		if (q == a.size() - 1) {
			rez.push_back(i - a.size() + 2);
			q = pi[q];
		}
	}
	ofstream out("strmatch.out");
	out << (rez.size() < 1000 ? rez.size() : 1000) << '\n';
	for (int i = 0; i < rez.size() && i < 1000; i++)
		out << rez[i] << ' ';
	in.close();
	out.close();
	return 0;
}

void calc()
{
	pi[1] = 0;
	int q = 0;
	for (int i = 2; i < a.size(); i++) {
		while (q && a[q + 1] != a[i])
			q = pi[q];
		if (a[q + 1] == a[i])
			q++;
		pi[i] = q;
	}
}