2 files changed, 37 insertions, 2 deletions
diff --git a/src/internal/bytealg/bytealg.go b/src/internal/bytealg/bytealg.go
index 4c90cd3671..6fd9308369 100644
--- a/src/internal/bytealg/bytealg.go
+++ b/src/internal/bytealg/bytealg.go
@@ -20,6 +20,7 @@ const (
 )
 
 // MaxLen is the maximum length of the string to be searched for (argument b) in Index.
+// If MaxLen is not 0, make sure MaxLen >= 4.
 var MaxLen int
 
 // FIXME: the logic of HashStrBytes, HashStrRevBytes, IndexRabinKarpBytes and HashStr, HashStrRev,
diff --git a/src/internal/bytealg/index_generic.go b/src/internal/bytealg/index_generic.go
index 98e859f925..83345f1013 100644
--- a/src/internal/bytealg/index_generic.go
+++ b/src/internal/bytealg/index_generic.go
@@ -16,8 +16,42 @@ func Index(a, b []byte) int {
 
 // IndexString returns the index of the first instance of b in a, or -1 if b is not present in a.
 // Requires 2 <= len(b) <= MaxLen.
-func IndexString(a, b string) int {
-	panic("unimplemented")
+func IndexString(s, substr string) int {
+	// This is a partial copy of strings.Index, here because bytes.IndexAny and bytes.LastIndexAny
+	// call bytealg.IndexString. Some platforms have an optimized assembly version of this function.
+	// This implementation is used for those that do not. Although the pure Go implementation here
+	// works for the case of len(b) > MaxLen, we do not require that its assembly implementation also
+	// supports the case of len(b) > MaxLen. And we do not guarantee that this function supports the
+	// case of len(b) > MaxLen.
+	n := len(substr)
+	c0 := substr[0]
+	c1 := substr[1]
+	i := 0
+	t := len(s) - n + 1
+	fails := 0
+	for i < t {
+		if s[i] != c0 {
+			o := IndexByteString(s[i:t], c0)
+			if o < 0 {
+				return -1
+			}
+			i += o
+		}
+		if s[i+1] == c1 && s[i:i+n] == substr {
+			return i
+		}
+		i++
+		fails++
+		if fails >= 4+i>>4 && i < t {
+			// See comment in src/bytes/bytes.go.
+			j := IndexRabinKarp(s[i:], substr)
+			if j < 0 {
+				return -1
+			}
+			return i + j
+		}
+	}
+	return -1
 }
 
 // Cutover reports the number of failures of IndexByte we should tolerate