Cod sursa(job #1691514)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 18 aprilie 2016 16:46:21
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;


int prf[100010];
vector<int> pozitii;
char * s;
char * d;

void prefix();
int search();


int main() {
	ifstream in("strmatch.in");
	s = new char[2000010];
	d = new char[2000010];
	in >> s + 1 >> d;
	ofstream out("strmatch.out");
	out << search() << '\n';
	for (auto i : pozitii)
		out << i << ' ';
	in.close();
	out.close();
	return 0;
}

int search() {
	int r = 0;
	prefix();
	s++;
	int n = strlen(s);
	int m = strlen(d);
	int i = 0;
	int k = 0;
	
	while (i <= m) {
		if (k == -1) {
			i++;
			k = 0;
		}
		else {
			if (d[i] == s[k]) {
				k++;
				i++;
				if (k == n) {
					if (pozitii.size() < 1000)
						pozitii.push_back(i - k);
					r++;
					k = prf[k];
				}
			}
			else
				k = prf[k];
		}
	}
	return r;
}


void prefix() {
	int l = strlen(s);
	prf[0] = -1;
	int k;
	for (int i = 1; i < l; i++) {
		k = prf[i - 1];
		while (k >= 0 && s[k + 1] != s[i])
			k = prf[k];
		prf[i] = k + 1;
	}
}