请你使用cpp写一个kmp算法，并详细讲解一下原理

KMP算法是一种字符串匹配算法，它的全称是Knuth-Morris-Pratt算法，是由Donald Knuth、James H. Morris和Vaughan Pratt三位计算机科学家于1977年联合发明的。

KMP算法的原理是利用已知信息尽可能地避免无效的比较，从而提高匹配效率。KMP算法的核心思想是：在匹配过程中，当出现不匹配的情况时，尽可能地利用已经匹配的信息，使模式串移动的距离尽量小。

具体地说，KMP算法首先构建一个next数组，next[i]表示模式串中以i结尾的前缀字符串中，前缀字符串的最长相等前缀和后缀的长度。例如，对于模式串"abababc"，next[7]=4，因为"abab"是"abababc"的前缀，也是后缀，长度为4。

构建next数组的过程可以采用递推的方式，假设已经求得next[0]至next[i-1]的值，现在要求next[i]的值。首先令j=next[i-1]，然后不断地向前查找，直到找到一个位置k满足p[k]=p[i-1]，此时令next[i]=j+1，否则如果j=0，则令next[i]=0。

构建好next数组后，就可以利用它来进行匹配。具体地说，对于文本串s和模式串p，假设当前匹配到文本串的第i个字符和模式串的第j个字符。如果s[i]=p[j]，则i和j都加1继续匹配；否则，假设现在要将模式串向右移动k个字符，那么应该将模式串中第j-k至第j-1个字符与模式串中第0至第k-1个字符进行比较，如果相等，则可以将模式串向右移动k个字符，继续匹配；否则，应该将模式串向右移动next[k]个字符，这样可以利用已经匹配的信息，避免无效的比较。

下面是KMP算法的cpp实现：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> getNext(string p) {
    int n = p.size();
    vector<int> next(n);
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < n; i++) {
        while (j > 0 && p[i] != p[j]) {
            j = next[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

int kmp(string s, string p) {
    int n = s.size(), m = p.size();
    vector<int> next = getNext(p);
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

int main() {
    string s = "hello world";
    string p = "world";
    int pos = kmp(s, p);
    if (pos == -1) {
        cout << "not found" << endl;
    } else {
        cout << "found at position " << pos << endl;
    }
    return 0;
}

以上代码中，getNext函数用来构建next数组，kmp函数用来进行匹配。时间复杂度为O(n+m)，其中n表示文本串长度，m表示模式串长度。