Underscorify Substring

• Time : O(n + m)
• Space : O(n + m)

using namespace std;

vector<int> PI(string& s) {
	int n = s.length();
	vector<int> pi(n);
	for(int i = 1, j = 0; i < n; i++) {
		while(j > 0 and s[i] != s[j]) j = pi[j - 1];
		if(s[i] == s[j])
			pi[i] = ++j;
	}
	return pi;
}

vector<int> kmp(string& s, string& p) {
	int n = s.length(), m = p.length();
	auto pi = PI(p);
	vector<int> res;
	for(int i = 0, j = 0; i < n; i++) {
		while(j > 0 and s[i] != p[j]) j = pi[j - 1];
		if(s[i] == p[j]) {
			if(++j == m) {
				res.push_back(i - j + 1);
				j = pi[j - 1];
			}
		}
	}
	return res;
}

string underscorifySubstring(string s, string p) {
  auto match = kmp(s, p);
	int plen = p.length();
	vector<int> in{INT_MIN}, out{INT_MIN};
	for(int i = 0; i < match.size(); i++) {
		if(in.back() + plen < match[i] and out.back() + 1 < match[i]) {
			in.push_back(match[i]);
			out.push_back(match[i] + plen - 1);
		} else {
			out.back() = match[i] + plen - 1;
		}
	}
	string res = "";
	for(int i = 0, j = 1, k = 1; i < s.length(); i++) {
		if(j < in.size() and in[j] == i) {
			res.push_back('_');
			j++;
		}
		res.push_back(s[i]);
		if(k < out.size() and out[k] == i) {
			res.push_back('_');
			k++;
		}
	}
  return res;
}