feat: 28 复习 KMP

chen-shiwei · chen-shiwei · commit dee361221899 · 2021-06-07T01:22:34.000+08:00
diff --git a/leetcode/28.实现strStr/strStr.go b/leetcode/28.实现strStr/strStr.go
@@ -1,7 +1,5 @@
 package _8_实现strStr
 
-import "fmt"
-
 func strStr(haystack string, needle string) int {
 	l1 := len(haystack)
 	l2 := len(needle)
@@ -25,8 +23,7 @@ func strStr(haystack string, needle string) int {
 func strStrWithKMP(haystack string, needle string) int {
 	l1 := len(haystack)
 	l2 := len(needle)
-
-	next := make([]int, l2)
+	var next = make([]int, l2)
 	for i, j := 1, 0; i < l2; i++ {
 		for j > 0 && needle[i] != needle[j] {
 			j = next[j-1]
@@ -36,7 +33,7 @@ func strStrWithKMP(haystack string, needle string) int {
 		}
 		next[i] = j
 	}
-	fmt.Println(next)
+
 	for i, j := 0, 0; i < l1; i++ {
 		for j > 0 && haystack[i] != needle[j] {
 			j = next[j-1]
@@ -49,4 +46,5 @@ func strStrWithKMP(haystack string, needle string) int {
 		}
 	}
 	return -1
+
 }
diff --git a/leetcode/28.实现strStr/strStr_test.go b/leetcode/28.实现strStr/strStr_test.go
@@ -30,7 +30,7 @@ func Test_strStr(t *testing.T) {
 		//	}
 		//})
 		t.Run(tt.name, func(t *testing.T) {
-			if got := strStrWithKMP(tt.args.haystack, tt.args.needle); got != tt.want {
+			if got := strStrWithKMP1(tt.args.haystack, tt.args.needle); got != tt.want {
 				t.Errorf("strStrWithKMP() = %v, want %v", got, tt.want)
 			}
 		})

Original file line number	Diff line number	Diff line change
`@@ -1,7 +1,5 @@`
`1`	`1`	`package _8_实现strStr`
`2`	`2`
`3`		`-import "fmt"`
`4`		`-`
`5`	`3`	`func strStr(haystack string, needle string) int {`
`6`	`4`	`l1 := len(haystack)`
`7`	`5`	`l2 := len(needle)`
`@@ -25,8 +23,7 @@ func strStr(haystack string, needle string) int {`
`25`	`23`	`func strStrWithKMP(haystack string, needle string) int {`
`26`	`24`	`l1 := len(haystack)`
`27`	`25`	`l2 := len(needle)`
`28`		`-`
`29`		`- next := make([]int, l2)`
	`26`	`+ var next = make([]int, l2)`
`30`	`27`	`for i, j := 1, 0; i < l2; i++ {`
`31`	`28`	`for j > 0 && needle[i] != needle[j] {`
`32`	`29`	`j = next[j-1]`
`@@ -36,7 +33,7 @@ func strStrWithKMP(haystack string, needle string) int {`
`36`	`33`	`}`
`37`	`34`	`next[i] = j`
`38`	`35`	`}`
`39`		`- fmt.Println(next)`
	`36`	`+`
`40`	`37`	`for i, j := 0, 0; i < l1; i++ {`
`41`	`38`	`for j > 0 && haystack[i] != needle[j] {`
`42`	`39`	`j = next[j-1]`
`@@ -49,4 +46,5 @@ func strStrWithKMP(haystack string, needle string) int {`
`49`	`46`	`}`
`50`	`47`	`}`
`51`	`48`	`return -1`
	`49`	`+`
`52`	`50`	`}`
Original file line number	Diff line number	Diff line change
`@@ -30,7 +30,7 @@ func Test_strStr(t *testing.T) {`
`30`	`30`	`// }`
`31`	`31`	`//})`
`32`	`32`	`t.Run(tt.name, func(t *testing.T) {`
`33`		`- if got := strStrWithKMP(tt.args.haystack, tt.args.needle); got != tt.want {`
	`33`	`+ if got := strStrWithKMP1(tt.args.haystack, tt.args.needle); got != tt.want {`
`34`	`34`	`t.Errorf("strStrWithKMP() = %v, want %v", got, tt.want)`
`35`	`35`	`}`
`36`	`36`	`})`