#include <stdio.h>

#include <stdlib.h>

#include <string.h>



#define MAX 255

typedef unsigned char SString[MAX+1];

int next[MAX];





/*

 * 0	:j == 1

 * k	:T[1...k-1] == T[j-(k-1)...j-1]

 * 1	:Others

 * */

void get_next(SString T, int next[])

{

	int i,j;

	i = 1;

	next[1] = 0;

	j = 0;

	while(i < T[0]){

		if(j == 0 || T[i] == T[j]){

			i++;

			j++;



#if 1			

			next[i] = j;

#else

			if(T[i] != T[j]){

				next[i] = j;

			}else{

				next[i] = next[j];

			}

#endif

		}else{

			j = next[j];

		}

	}

}



int Index_kmp(SString S, SString T, int pos)

{

	int i,j;

	i = pos;

	j = 1;

	while(i<=S[0] && j<=T[0]){

		if(j == 0 || S[i] == T[j]){

			i++;

			j++;

		}else{

			j = next[j];

		}

	}

	if(j>T[0]){

		return i-T[0];

	}else{

		return 0;

	}

}



void main()

{

	char *original_t = "abaabc";

	char *original_s = "aaaaabaabcbbbb";

	SString T,S;



	int i;



	printf("log.anycle.com\n\n");



	printf("Original data:\n");

	printf("S:%s\n", original_s);

	printf("T:%s\n", original_t);

	memcpy(T+1, original_t, strlen(original_t));

	memcpy(S+1, original_s, strlen(original_s));

	T[0] = strlen(original_t);

	S[0] = strlen(original_s);



	printf("Get next of T:\n");

	get_next(T, next);

	for(i=1; i<=T[0]; i++){

		printf(" %d", next[i]);

	}

	printf("\n");



	printf("Get position of T in S:\n");

	printf(" %d\n", Index_kmp(S, T, 0));

}