KMPアルゴリズムnext配列再帰求法

//                 +-------+---+-+
//                 |  ...  |i-1|i|   Next(array, i)
//                 +-------+---+-+
//                       X
//                      / \      -------+
//                     /   \     |      |
//                    /     \    |      |
//  i-1      +---+|      |---|v|---|---|    i-1     ，
//           | i-1|      |...|j|...|i-1|     j=Next(i-1)，
//            +----|      |---|-|---|-|-|     array[i-1] array[j]
//                  /           /   \   |
//                 /           /     \  |----|
//                /           /       \      |
//               0          j+1       ------|v|----      array[i-1] array[j]  ，
//                                    | ... |j|j+1|      array[i-1]  array[j] 
//                                    +-----+-+----       Next(array, j+1)                              
#include <stdio.h>
#include <string.h>
int Next(char array[], int i)
{
	int ret = 0;
	if ( 0 == i )
		ret = -1;
	else if ( i == 1 )
		ret = 0;
	else
	{
		int j = 0;
		int t = 0;

		j = Next( array, i-1);
		if ( array[j] == array[i-1] )
			ret = j+1;
		else
		{
			t = array[i-1];
			array[i-1] = array[j];
			array[j] = t;

			ret = Next(array, j+1);

			t = array[i-1];
			array[i-1] = array[j];
			array[j] = t;
		}
	}
	return ret;
}

void main()
{
	int i = 0;
	char str[] = "abaabcac";

	for ( i=0; i<strlen(str); i++ )
		printf("%d ", Next(str, i));
}