Cod sursa(job #1213317)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 27 iulie 2014 20:12:31
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <string>
#define NMAX 2000001
#define RMAX 1000

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int t[NMAX], pos[NMAX], nr;

int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

void build_table(string s, int n) {
	int m = 0;
	t[0] = -1;
	for (int i = 1; i < n; ++i) {
		t[i] = m;
		if (s[i] == s[m]) {
			m++;
		}
		else {
			m = 0;
		}
	}
}

void find_occurences(string w, string s) {
	int m = 0, n = w.length();
	nr = 0;

	for (int i = 0; i + n - m - 1 < s.length(); ++i) {
		if (w[m] == s[i]) {
			m++;
			if (m == n) {
				pos[nr++] = i - m + 1;
				m = t[m];
				if (m != -1) {
					i--;
				}
				else {
					m = 0;
				}
			}
		}
		else {
			m = t[m];
			if (m != -1) {
				i--;
			}
			else {
				m = 0;
			}
		}
	}
}

int main() {

	string a, b;

	f >> a >> b;

	build_table(a, a.length());

	/*/
	for (int i = 0; i < a.length(); ++i) {
		g << t[i] << " ";
	}
	//*/

	find_occurences(a, b);

	g << nr << "\n";
	for (int i = 0; i < min(nr, RMAX); ++i) {
		g << pos[i] << " ";
	}
	

	return 0;
}