#include <iostream>
#include <string>
#include <array>

std::array<int, 1000000U> prefix;

size_t prefixSize = 0U;

void MakePrefix(const std::string& substr)
{
	size_t i, j = 0U;
	prefix[0U] = 0;

	for(i = 1U; i < substr.size();) {
		if(substr[i] == substr[j]) {
			prefix[i] = j + 1;
			++i, ++j;
		}
		else if(j > 0U) {
			j = prefix[j - 1U];
		}
		else {
			prefix[i] = 0;
			++i;
		}
	}

	prefixSize = i;
}

std::array<int, 1001U> index;
size_t lastIndex = 0U;

void KMP(const std::string& substr, const std::string& fullstr)
{
	size_t offset = 0U;

	for(size_t i = 0U; i < fullstr.size();) {
		if(substr[offset] == fullstr[i] && offset == prefixSize - 1U) {
			if(lastIndex < 1000) {
				index[lastIndex++] = i - offset;
			}
			else 
				break;

			if(offset > 0U) {
				offset = prefix[offset - 1U];
			}
		}
		else if(substr[offset] == fullstr[i]) {
			++i, ++offset;
		}
		else {
			++i;
		}
	}
}

int main(int argc, char * argv[])
{
	std::string fullstr("ABABCDABABABFG");
	std::string substr("ABA");

	MakePrefix(substr);
	KMP(substr, fullstr);

	return 0;
}