#include <bits/stdc++.h>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>

using namespace std;

void get_next(string s,vector<int> &next)
{
    next[1]=0;
    next[2]=1;
    int k,j;
    j=2;
    while(1)
    {
        if(j >= next.size()-1)  //到达最后的字符就退出循环
            break;
        //以下代码设法求 j+1 位的next值

        k = next[j];  //先让 k 取 j 位的next值
        while(k!=0)   //当 k 不是第0位，s[j] 也不等于 s[k] 时
        {
            if(s[j] == s[k])
                break;
            else
                k = next[k]; //回溯
        }
        next[j+1]=k+1;  // j+1 位的 next值 等于 k+1
        j++;  //再求下一位的next
    }
}

void get_nextVal(string p,vector<int> next,vector<int> &nextVal)  //在已有next的基础上，求修正值
{
    nextVal = next; //赋初值
    int j, k;
    for(j=2; j<nextVal.size(); j++)
    {
        k = nextVal[j];	   //先让 k 取 j 位的next值
        //1：当 j 位和 k 位字符不相等时，nextVal[j]就取next[j]的值

        while(p[j] == p[k])  //2: 当 j 位和 k 位字符相等时
        {
            k = nextVal[k];  //回溯直到 j 位和 k 位字符不再相等
            nextVal[j] = k;  //使 j 位的 nextVal = k
        }
    }
}

int main(void)
{
    string p="$abaabcac";

	cout << "模式串为："  << endl;
	for(int i=1; i <= p.size()-1; i++)
		cout << p[i] << "  ";
	cout << endl;

	//计算next函数
	vector<int> next;
	next.resize(p.size());
    get_next(p,next);

    //输出对应next函数值
    for(int i=1; i<=next.size()-1; i++)
		cout << next[i] << "  ";
	cout << endl;

	//计算next函数修正值
    vector<int> nextVal;
    get_nextVal(p, next, nextVal);

	for(int i=1;i<=nextVal.size()-1;i++)
		cout << nextVal[i] << "  ";
	cout << endl;
	return 0;
}