*** backend/utils/adt/varlena.c.orig	2007-08-01 05:32:22.000000000 +0500
--- backend/utils/adt/varlena.c	2007-08-01 05:10:32.000000000 +0500
***************
*** 40,45 ****
--- 40,46 ----
  	pg_wchar   *wstr2;			/* note: these are palloc'd */
  	int			len1;			/* string lengths in logical characters */
  	int			len2;
+ 	int	   *p;				/*   for Knuth-Morrison-Pratt alogrithm*/
  } TextPositionState;
  
  #define DatumGetUnknownP(X)			((unknown *) PG_DETOAST_DATUM(X))
***************
*** 62,67 ****
--- 63,70 ----
  static int	text_position(text *t1, text *t2);
  static void text_position_setup(text *t1, text *t2, TextPositionState *state);
  static int	text_position_next(int start_pos, TextPositionState *state);
+ static void 	init_kmp(TextPositionState *state);
+ static int	kmp(int start_pos, TextPositionState *state);
  static void text_position_cleanup(TextPositionState *state);
  static text *text_substring(Datum str,
  			   int32 start,
***************
*** 805,810 ****
--- 808,856 ----
   * variable is normally just a local variable in the caller.
   */
  
+ /* Knuth-Morrison-Pratt algorithm
+  * init procedure for KMP
+  * see T. Cormen et. al. [2001] Introduction to Algorithms
+  */
+ static void init_kmp(TextPositionState *state)
+ {
+     int *p;
+     int q, k, len;
+     char *str;
+     pg_wchar *wstr;
+     
+     k = -1;
+     p = state->p;
+     p[0] = -1;
+     
+     len = state->len2;
+     if (!state->use_wchar)
+     {
+         str = state->str2;
+         for (q = 1; q < len; q++)
+         {
+           while (k > -1 && str[k + 1] != str[q])
+             k = p[k];
+             if (str[k + 1] == str[q])
+               k++;
+             p[q] = k;
+         }
+     }
+     else
+     {
+ 	/* multibyte encoding - the same*/
+ 	wstr = state->wstr2;
+         for (q = 1; q < len; q++)
+         {
+           while (k > -1 && wstr[k + 1] != wstr[q])
+             k = p[k];
+           if (wstr[k + 1] == wstr[q])
+             k++;
+           p[q] = k;
+         }
+     }	
+ }
+ 
  static void
  text_position_setup(text *t1, text *t2, TextPositionState *state)
  {
***************
*** 819,824 ****
--- 865,873 ----
  		state->str2 = VARDATA(t2);
  		state->len1 = len1;
  		state->len2 = len2;
+ 		
+ 		state->p = (int *) palloc (state->len2 * sizeof(int));
+ 		init_kmp(state);
  	}
  	else
  	{
***************
*** 836,898 ****
  		state->wstr2 = p2;
  		state->len1 = len1;
  		state->len2 = len2;
  	}
  }
  
  static int
  text_position_next(int start_pos, TextPositionState *state)
  {
! 	int			pos = 0,
! 				p,
! 				px;
  
  	Assert(start_pos > 0);		/* else caller error */
  
  	if (state->len2 <= 0)
  		return start_pos;		/* result for empty pattern */
  
! 	if (!state->use_wchar)
! 	{
! 		/* simple case - single byte encoding */
! 		char	   *p1 = state->str1;
! 		char	   *p2 = state->str2;
! 
! 		/* no use in searching str past point where search_str will fit */
! 		px = (state->len1 - state->len2);
! 
! 		p1 += start_pos - 1;
! 
! 		for (p = start_pos - 1; p <= px; p++)
! 		{
! 			if ((*p1 == *p2) && (strncmp(p1, p2, state->len2) == 0))
! 			{
! 				pos = p + 1;
! 				break;
! 			}
! 			p1++;
! 		}
! 	}
! 	else
! 	{
! 		/* not as simple - multibyte encoding */
! 		pg_wchar   *p1 = state->wstr1;
! 		pg_wchar   *p2 = state->wstr2;
! 
! 		/* no use in searching str past point where search_str will fit */
! 		px = (state->len1 - state->len2);
! 
! 		p1 += start_pos - 1;
! 
! 		for (p = start_pos - 1; p <= px; p++)
! 		{
! 			if ((*p1 == *p2) && (pg_wchar_strncmp(p1, p2, state->len2) == 0))
! 			{
! 				pos = p + 1;
! 				break;
! 			}
! 			p1++;
! 		}
! 	}
  
  	return pos;
  }
--- 885,954 ----
  		state->wstr2 = p2;
  		state->len1 = len1;
  		state->len2 = len2;
+ 
+ 		state->p = (int *) palloc(state->len2 * sizeof(int));
+ 		init_kmp(state);
  	}
  }
  
+ static int kmp(int start_pos, TextPositionState *state)
+ {
+     int i, k, len1, len2;
+     char *str1, *str2;
+     pg_wchar *wstr1, *wstr2;
+     int *p;
+     
+     k = -1;			/* init state */
+     len2 =  state->len2;
+     len1 =  state->len1;
+     p = state->p;
+     
+     if (!state->use_wchar)
+     {
+         str1 = state->str1 + start_pos - 1;
+         str2 = state->str2;
+         for (i = 0; i < len1 - start_pos + 1; i++)
+         {
+             while (k > -1 && str2[k + 1] != str1[i])
+         	    k = p[k];	
+     	    if (str2[k + 1] == str1[i])
+     		k++;
+     	    if (k == len2 - 1)
+     		return (i - len2 + 2) + start_pos - 1;
+ 	}
+     }
+     else
+     {
+ 	/* multibyte encoding - the same */
+         wstr1 = state->wstr1 + start_pos - 1;
+         wstr2 = state->wstr2;
+     
+         for (i = 0; i < len1 - start_pos + 1; i++)
+         {
+             while (k > -1 && wstr2[k + 1] != wstr1[i])
+         	k = p[k];	
+     	    if (wstr2[k + 1] == wstr1[i])
+     		k++;
+     	    if (k == len2 - 1)
+     		return (i - len2 + 2) + start_pos - 1;
+ 	}
+     }
+     
+     return 0;			/* not found */
+ }
+ 
+ 
  static int
  text_position_next(int start_pos, TextPositionState *state)
  {
! 	int pos = 0;
  
  	Assert(start_pos > 0);		/* else caller error */
  
  	if (state->len2 <= 0)
  		return start_pos;		/* result for empty pattern */
  
!         pos = kmp(start_pos, state);
  
  	return pos;
  }
***************
*** 900,905 ****
--- 956,962 ----
  static void
  text_position_cleanup(TextPositionState *state)
  {
+ 	pfree(state->p);
  	if (state->use_wchar)
  	{
  		pfree(state->wstr1);