Knuth-Morris-Pratt algorithm

int KMP(std::string &pattern, std::string &word)
{
    // Compute the partial match table
    std::vector<int> part_match(pattern.size());
    part_match[0] = 0;

    for(int i = 1; i < pattern.size(); i++)
    {
        // Start with the previous partial match
        part_match[i] = part_match[i - 1];

        // Jump back until a partial match at the current position is found
        while(part_match[i] > 0 && pattern[i] != pattern[part_match[i]])
            part_match[i] = part_match[part_match[i] - 1];

        // Increment the partial match if it's non-zero
        if(pattern[i] == pattern[part_match[i]])
            part_match[i]++;
    }

    // Find a match
    for(int i = 0, j = 0; i < word.size(); i++)
    {
        // Jump back until a partial match at the current position is found
        while(j > 0 && word[i] != pattern[j])
            j = part_match[j - 1];

        // If it's a full match, return its position
        if(word[i] == pattern[j] && ++j == pattern.size())
            return i - j + 1;
    }

    // No full matches found
    return -1;
}