优化版

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, M = 1000010;

string str=" ababaaababaa";

int ne[N];

int main() {

    // 求next数组
    for(int i=1,j=0;i<int(str.size());){
        if(j==0||str[i]==str[j]){
            i++,j++;
            ne[i]=j;
            if(str[i]!=str[j])
                ne[i]=j;
            else
                ne[i]=ne[j];
        }else{
            j=ne[j];
        }
    }

    for(int i=1;i<int(str.size());i++)
        cout<<ne[i]<<" ";

    return 0;
}

未优化版

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010, M = 1000010;

string str=" ababaaababaa";

int ne[N];

int main() {

    for(int i=1,j=0;i<int(str.size());){
        if(j==0||str[i]==str[j]){
            i++,j++;
            ne[i]=j;
            /* 区别
             * if(str[i]!=str[j])
             *     ne[i]=j;
             * else
             *     ne[i]=ne[j];
             */
        }else{
            j=ne[j];
        }
    }

    for(int i=1;i<int(str.size());i++)
        cout<<ne[i]<<" ";

    return 0;
}