kmp-instructive.cpp

vector<int> kmp(string s, string w) {
	vector<int> T(w.size() + 1, 0), matches;
	T[0] = -1, T[1] = 0; // default values, will never change
	int pos = 0; 

	for (int i = 2; i <= w.size(); ++i) {
	    if (w[i - 1] == w[pos]) { // keep matching, and if we ever failing at position i - 1, we've matched pos characters
	    	++pos;
	    	T[i] = pos;
	    }
	    else if (pos > 0) { // we failed, let's fall back to T[pos]
	    	pos = T[pos];
	    	--i;
	    }
	    else { // we can't do anything about it, if we fail here we have to go back to start
	    	T[i] = 0;
	    }
	}

	int i = 0, j = 0;
	while (i < s.size()) { // Let's try to see if at i we find w in s.
		if (j == -1) ++j; 
		if (s[i + j] == w[j]) { 
			if (j == w.size() - 1) { // w is found completely as a substring s[i]s[i+1]s[i+2]...s[i+|w|-1]
				matches.push_back(i);
				j = T[j]; // fall back to the start of the next possible match
				++i; //
			}
			else ++j;
		}
		else if (T[j] > -1) { // didn't match but we can fall somewhere, go.
			i = i + j - T[j];
			j = T[j];
		}
		else { // nothing to do
			j = 0;
			++i;
		}
	}
	
	return matches;
}