lab5 / KMP

#include "KMP.h"

vector<lli> prefixFunction(string &pattern) {
	vector<lli> p(pattern.size(), 0);

	for (lli k = 0, i = 1, s = pattern.size(); i < s; ++i) {
		while ((k > 0) && (pattern[i] != pattern[k]))
			k = p[k - 1];

		if (pattern[i] == pattern[k])
			k++;

		p[i] = k;
	}

	return p;
}

vector<lli> KMP(string &text, string &pattern) {
	vector<lli> p = prefixFunction(pattern), sol;

	for (lli i = 0, k = 0, st = text.size(), sp = pattern.size(); i < st; ++i) {
		while (k > 0 && pattern[k] != text[i])
			k = p[k - 1];
		if (text[i] == pattern[k])
			k++;
		if (k == sp)
			sol.push_back(i - k + 1);
	}

	return sol;
}

lli findFirstCyclicShift(string &text, string &pattern) {
	string concat = (pattern + "&" + text), backConcat = (text + "&" + pattern);

	lli i = prefixFunction(concat).back();

	if (i == text.size())
		return 0;

	return i + prefixFunction(backConcat).back() == text.size() ? i: -1;
}