#include <iostream>
#include <cstring>
using namespace std;
int index(char *s, char *t);
void get_next(char *s, int tlen, int next[]);

int main()
{
	char s[] = "acabaabaabcacaabc";
	char t[] = "abaabc";
	cout << "Position: " << index(s, t) << endl;
}
int index(char *s, char *t)
{
	int i=1, j=1;
	int slen = strlen(s);
	int tlen = strlen(t);
	int next[tlen+1];
	get_next(t, tlen, next);
	while(i<=slen && j<=tlen)
	{
		if(j==0 || s[i-1]==t[j-1])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if(j>tlen)
		return i-tlen;
	else
		return -1;
}
void get_next(char *t, int tlen, int next[])
{
	int i=1, j=0;
	next[1] = 0;
	while(i<tlen)
	{
		if(j==0 || t[i-1]==t[j-1])
		{
			i++;
			j++;
			if(t[i-1] != t[j-1])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
			}
		}
		else
		{
			j = next[j];
		}
	}
}