kmp.sublime-snippet

<snippet>
	<content><![CDATA[
// code credit : https://github.com/spaghetti-source/algorithm/blob/master/string/knuth_morris_pratt.cc
struct knuth_morris_pratt {
  int m;
  const char *p;
  vector<int> fail;
  knuth_morris_pratt(const char *p) : p(p), m(strlen(p)) {
    fail.resize(m+1, -1);
    for (int i = 1, j = -1; i <= m; ++i) {
      while (j >= 0 && p[j] != p[i-1]) j = fail[j];
      fail[i] = ++j;
    }
  }
  vector<int> match(const char *s) {
    int n = strlen(s);
    vector<int> occur;
    for (int i = 0, k = 0; i < n; ++i) {
      while (k >= 0 && s[i] != p[k]) k = fail[k];
      if (++k == m) { 
        /* match at s[i-m+1 ... i] */
        occur.push_back(i-m+1);
      }
    }
    return occur;
  }
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>knuth</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<scope>source.cpp, source.c++, source.c</scope>
	<!-- Optional: Description to show in the menu -->
	<description>Knuth-Patt-Morris Algorithm</description>
</snippet>