#include<bits/stdc++.h>

using namespace std;
#define int long long 
pair<string,int> SqString;

void GetNext(pair<string,int> SqStringt,int next[]){
	int j,k;
	j=0,k=-1;
	next[0]=-1;
	while(j<(SqString.second)-1){
		if(k==-1||SqString.first[j]==SqString.first[k]){
			j++;
			k++;
			next[j]=k;
		}else{
			k=next[k];
		}
	}
}

int KMPIndex(pair<string,int>s,pair<string,int>SqString t){
	int next[500],i=0,j=0;
	GetNext(t,next);
	while(i<s.second&&j<t.second){
		if(j==-1||s.first[i]=t.first[j]){
			i++,j++;
		}else j=next[j];
	}
	if(j>=t.second)
		return (i-t.second);
	else 
		return -1;
}

signed main()
{
	int next[9];
	memset(next,0,sizeof(next));
	SqString={"abcabcmm",8};
	GetNext(SqString,next);
	for(int i=0;i<9;++i) 
		printf("next[%d]=%d\n",i,next[i]);
	return 0;
}