Skip to content

Instantly share code, notes, and snippets.

@agasiev
Created December 6, 2012 23:24
Show Gist options
  • Save agasiev/4229378 to your computer and use it in GitHub Desktop.
Save agasiev/4229378 to your computer and use it in GitHub Desktop.
KMP prefix function
std::vector<unsigned> kmp_prefix_function(std::string s) {
size_t n = s.size();
std::vector<unsigned> result(n);
for (int i = 1; i < n; i++) {
int j = result[i-1];
while (j > 0 && s[i] != s[j])
j = result[j-1];
if (s[i] == s[j]) j++;
result[i] = j;
}
return result;
}
int main(int argc, char ** argv) {
std::vector<unsigned> a = kmp_prefix_function("abcabcd");
for (int i = 0; i < a.size(); i++)
std::cout << a[i] << " ";
std::cout << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment