モードマッチングKMPアルゴリズム(Java)

/********       **********/
//   、        
//  childstr mumstr  pos        ，     ，   0
public int FindStr(String mumstr, String childstr, int pos)
{
	//         
	
	if((childstr.length() > mumstr.length()) || (pos >= mumstr.length()))
		return 0;
	
	char[] mumarr = mumstr.toCharArray();
	char[] childarr = childstr.toCharArray();
	int i = pos;
	int j = 0;
	
	while((i < mumarr.length) && ( j < childarr.length))
	{
		//      
		if( mumarr[i] == childarr[j])
		{
			++i;
			++j;
		}
		//     ，       
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	
	//        ，      ，           j = childarr.length  
	if( j >= childarr.length)
	{
		return i - j;
	}
	return 0;
}

/**************KMP  *****************/
//KMP               ，    next[j],        next[j]   i           

//next[j]    
/*   next[1] = 0;(           str            )
       next[j] ，       j-1    
  next[j]         ： next[j] = k; 
  1.str[j] = str[k], next[j + 1] = next[j] + 1 = k + 1;
  2.   ，                childstr     。    str[j]  str[next[k]]    （   next[j] = k）;
    1)   ， next[j + 1] = next[k] + 1 = k' + 1;
	2)    ，    next[k] = k', str[j] str[k' + 1]   ；
*/
private int[] getNext(String childstr)
{
	//     
	int length = childstr.length();
	char[] childarr = childstr.toCharArray();
	int next[] = new int[length];
	next[0] = -1;//         
	int i = 0;
	int j = -1;
	
	while ( i < length - 1)
	{
		if( i == 0 || j == -1 ||childarr[i] == childarr[j])//      j=-1     
		{
			next[++i] = ++j;
		}
		else
		{
			j = next[j]; 
		}
	}	
	return next;
}
/*******************KMP  ********************/
public int IndexKMP(String mumstr, String childstr, int pos)
{
	if((childstr.length() > mumstr.length()) || (pos >= mumstr.length()))
		return 0;
	
	char[] mumarr = mumstr.toCharArray();
	char[] childarr = childstr.toCharArray();
	int i = pos;
	int j = 0;
	int[] next = getNext(childstr);
	
	while ((i < mumarr.length)&&(j < childarr.length))
	{
		if(j == -1 || mumarr[i] == childarr[j])//      j=-1       
		{
			++i;
			++j;
		}
		else
		{
			//i  ，j  next[j]
			j = next[j];
		}
	}		
	
	if ( j >= childarr.length)
	{
		return i - j;
	}
	return 0;	
}

public static void main(String[] args) {
	StrMatch strMatch = new StrMatch();
	String aString = "ababccddefgabcdefghij";
	String bString = "ababccddefg";
	
	System.out.println(strMatch.IndexKMP(aString, bString, 3));

}


/********   nextval  ********/
/*         a  a  a  a  b    
     next[j]  0  1  2  3  4
    nextval[j]0  0  0  0  1
	
	     b   ，   next[4] = 3  ，  a,        next[3] = 2;     a,       
	             a  ；
	
	      ，next[j] = k;  str[j] = str[k],   str[next[k]]    ， str[j] = str[next[k]],     ，
	  str[j]     ； next[j] = next[k],          

*/

private int[] nextval(String childstr)
{
	//     
	int length = childstr.length();
	char[] childarr = childstr.toCharArray();
	int next[] = new int[length];
	next[0] = -1;//         
	int i = 0;
	int j = -1;
	
	while ( i < length - 1)
	{
		if( i == 0 || j == -1 ||childarr[i] == childarr[j])//      j=-1     
		{
			++i;
			++j;
			//            
			if(childarr[i] == childarr[j])//  next[j] = next[k]  
			{
				next[i] = next[j];
			}
			else
			{
				next[i] = j;
			}
		}
		else
		{
			j = next[j]; 
		}
	}	
	return next;
}