KMP 알고리즘 GO 구현

KMP 알고리즘 의 핵심 은 next 의 배열 next 배열 에 저 장 된 값 을 구 하 는 것 입 니 다. 실패 한 후에 하위 문자열 이 거 슬러 올 라 갈 위치 네트워크 의 예 를 들 어 next 는 작은 편차 가 있 고 최종 적 으로 실현 되 는 효 과 는 똑 같 습 니 다. 참고 링크:https://www.cnblogs.com/dusf/p/kmp.html

//       
func Sindex(S,T string) int {
	i := 0
	j := 0
	//                      
	for ;i <= len(S) -1  && j <= len(T) -1;{
		if S[i] == T[j]{
			//       i j   1
			i++
			j++
		}else{
			//    j            0   i              
			i = i -j +1
			j = 0
		}
	}
	//   j          T           
	if j >= len(T) -1 {
			return i - len(T) +1
		}

	return 0
}

//next     
func get_next(T string) [20]int {
	var i,j int
	var next [20]int
	i = 0
	j = -1
	next[0] = -1
	for ;i<len(T)-1; {
		
		if j == -1 || T[i] == T[j]{
			
			j++
			i++
			if T[i] == T[j] {
				next[i] = next[j]
			}else{
				next[i] = j
			
			}
			
			
		}else{
			
			j = next[j]
		}
		
	}
	return next
}

//KMP      
func SindexKMP(S,T string) int {
	next := get_next(T)
	fmt.Println(next)
	i := 0
	j := 0
	//                      
	for ;i <= len(S) -1  && j <= len(T) -1;{
		
		if j == -1|| S[i] == T[j]{
			//       i j   1
			i++
			j++
		}else{
			//         next      i   
			j = next[j]
		}
	}
	//   j          T           
	if j >= len(T) -1 {
		return i - len(T) +1
	}

	return 0
}