Added my solution algorithmFive to elvis problem. Similar to Tyler's algorithmFour, but slightly slower.

benchmark_results.txt

go test -run none -bench . -benchtime 3s -benchmem
testing: warning: no tests to run
PASS
BenchmarkAlgorithmOne-8      2000000          2590 ns/op          53 B/op          2 allocs/op
BenchmarkAlgorithmTwo-8      5000000           957 ns/op           0 B/op          0 allocs/op
BenchmarkAlgorithmThree-8    3000000          1470 ns/op          16 B/op          1 allocs/op
BenchmarkAlgorithmFour-8     2000000          1907 ns/op           1 B/op          1 allocs/op
BenchmarkAlgorithmFive-8     2000000          2026 ns/op           1 B/op          1 allocs/op
BenchmarkAlgorithmSix-8      2000000          2177 ns/op          16 B/op          1 allocs/op
BenchmarkAlgorithmSeven-8    2000000          1878 ns/op         176 B/op          3 allocs/op

main.go

// All material is licensed under the Apache License Version 2.0, January 2004
// http://www.apache.org/licenses/LICENSE-2.0

// Sample program that takes a stream of bytes and looks for the bytes
// “elvis” and when they are found, replace them with “Elvis”. The code
// cannot assume that there are any line feeds or other delimiters in the
// stream and the code must assume that the stream is of any arbitrary length.
// The solution cannot meaningfully buffer to the end of the stream and
// then process the replacement.
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
)

// data represents a table of input and expected output.
var data = []struct {
	input  []byte
	output []byte
}{
	{[]byte("abc"), []byte("abc")},
	{[]byte("elvis"), []byte("Elvis")},
	{[]byte("aElvis"), []byte("aElvis")},
	{[]byte("abcelvis"), []byte("abcElvis")},
	{[]byte("eelvis"), []byte("eElvis")},
	{[]byte("aelvis"), []byte("aElvis")},
	{[]byte("aabeeeelvis"), []byte("aabeeeElvis")},
	{[]byte("e l v i s"), []byte("e l v i s")},
	{[]byte("aa bb e l v i saa"), []byte("aa bb e l v i saa")},
	{[]byte(" elvi s"), []byte(" elvi s")},
	{[]byte("elvielvis"), []byte("elviElvis")},
	{[]byte("elvielvielviselvi1"), []byte("elvielviElviselvi1")},
	{[]byte("elvielviselvis"), []byte("elviElvisElvis")},
}

// Declare what needs to be found and its replacement.
var find = []byte("elvis")
var repl = []byte("Elvis")

// Calculate the number of bytes we need to locate.
var size = len(find)

func main() {
	var output bytes.Buffer

	fmt.Println("=======================================\nRunning Algorithm One")
	for _, d := range data {
		output.Reset()
		algorithmOne(d.input, &output)
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}

	fmt.Println("=======================================\nRunning Algorithm Two")
	for _, d := range data {
		output.Reset()
		algorithmTwo(d.input, &output)
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}

	fmt.Println("=======================================\nRunning Algorithm Three")
	for _, d := range data {
		output.Reset()
		algorithmThree(bytes.NewReader(d.input), &output)
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}

	fmt.Println("=======================================\nRunning Algorithm Four")
	for _, d := range data {
		output.Reset()
		algorithmFour(bytes.NewReader(d.input), &output)
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}

	fmt.Println("=======================================\nRunning Algorithm Five")
	for _, d := range data {
		output.Reset()
		algorithmFive(bytes.NewReader(d.input), &output)
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}

	fmt.Println("=======================================\nRunning Algorithm Six")
	for _, d := range data {
		output.Reset()
		algorithmSix(bytes.NewReader(d.input), &output)
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}

	fmt.Println("=======================================\nRunning Algorithm Seven")
	for _, d := range data {
		output.Reset()
		output.ReadFrom(NewReplaceReader(bytes.NewReader(d.input), find, repl))
		matched := bytes.Compare(d.output, output.Bytes())
		fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
	}
}

// algorithmOne is one way to solve the problem.
func algorithmOne(data []byte, output *bytes.Buffer) {

	// Use a bytes Reader to provide a stream to process.
	input := bytes.NewReader(data)

	// Declare the buffer we need to process the stream.
	buf := make([]byte, size)
	end := size - 1

	// Read in an initial number of bytes we need to get started.
	if n, err := io.ReadFull(input, buf[:end]); err != nil {
		output.Write(buf[:n])
		return
	}

	for {

		// Read in one byte from the input stream.
		b, err := input.ReadByte()
		if err != nil {

			// Flush the reset of the bytes we have.
			output.Write(buf[:end])
			break
		}

		// Add this byte to the end of the buffer.
		buf[end] = b

		// If we have a match, replace the bytes.
		if bytes.Compare(buf, find) == 0 {
			copy(buf, repl)
		}

		// Write the front byte since it has been compared.
		output.WriteByte(buf[0])

		// Slice that front byte out.
		copy(buf, buf[1:])
	}
}

// algorithmTwo is a second way to solve the problem.
// Provided by Tyler Bunnell https://twitter.com/TylerJBunnell
func algorithmTwo(data []byte, output *bytes.Buffer) {

	// Use the bytes Reader to provide a stream to process.
	input := bytes.NewReader(data)

	// Create an index variable to match bytes.
	idx := 0

	for {

		// Read a single byte from our input.
		b, err := input.ReadByte()
		if err != nil {
			break
		}

		// Does this byte match the byte at this offset?
		if b == find[idx] {

			// It matches so increment the index position.
			idx++

			// If every byte has been matched, write
			// out the replacement.
			if idx == size {
				output.Write(repl)
				idx = 0
			}

			continue
		}

		// Did we have any sort of match on any given byte?
		if idx != 0 {

			// Write what we've matched up to this point.
			output.Write(find[:idx])

			// Unread the unmatched byte so it can be processed again.
			input.UnreadByte()

			// Reset the offset to start matching from the beginning.
			idx = 0

			continue
		}

		// There was no previous match. Write byte and reset.
		output.WriteByte(b)
		idx = 0
	}
}

// algorithmThree is a second way to solve the problem. This approach takes an
// io.Reader to represent an infinite stream. This allows for the algorithm to
// accept input from just about anywhere, thanks to the beauty of Go
// interfaces.
//
// Provided by Tyler Bunnell https://twitter.com/TylerJBunnell
func algorithmThree(data io.Reader, output *bytes.Buffer) {

	// Use bufio.NewReaderSize to provide a stream from which we can read and
	// unread single bytes.
	input := bufio.NewReaderSize(data, 1)

	// Create an index variable to match bytes.
	idx := 0

	for {

		// Read a single byte from our input.
		b, err := input.ReadByte()
		if err != nil {
			break
		}

		// Does this byte match the byte at this offset?
		if b == find[idx] {

			// It matches so increment the index position.
			idx++

			// If every byte has been matched, write
			// out the replacement.
			if idx == size {
				output.Write(repl)
				idx = 0
			}

			continue
		}

		// Did we have any sort of match on any given byte?
		if idx != 0 {

			// Write what we've matched up to this point.
			output.Write(find[:idx])

			// Unread the unmatched byte so it can be processed again.
			input.UnreadByte()

			// Reset the offset to start matching from the beginning.
			idx = 0

			continue
		}

		// There was no previous match. Write byte and reset.
		output.WriteByte(b)
		idx = 0
	}
}

// algorithmFour is a fourth way to solve the problem. This approach takes an
// io.Reader to represent an infinite stream. This allows for the algorithm to
// accept input from just about anywhere, thanks to the beauty of Go
// interfaces.
//
// Additionally, it has been optimized for minimal allocations by reading
// directly from the stream onto the stack. This results in 1 allocation of 1
// byte at the time of writing.
//
// Provided by Tyler Bunnell https://twitter.com/TylerJBunnell
func algorithmFour(data io.Reader, output *bytes.Buffer) {

	// Create a byte slice of length 1 into which our byte will be read.
	b := make([]byte, 1)

	// Create an index variable to match bytes.
	idx := 0

	for {

		// Are we re-using the byte from a previous call?
		if b[0] == 0 {
			// Read a single byte from our input.
			n, err := data.Read(b)
			if n == 0 || err != nil {
				break
			}
		}

		// Does this byte match the byte at this offset?
		if b[0] == find[idx] {

			// It matches so increment the index position.
			idx++

			// If every byte has been matched, write
			// out the replacement.
			if idx == size {
				output.Write(repl)
				idx = 0
			}

			// Reset the reader byte to 0 so another byte will be read.
			b[0] = 0
			continue
		}

		// Did we have any sort of match on any given byte?
		if idx != 0 {

			// Write what we've matched up to this point.
			output.Write(find[:idx])

			// NOTE: we are NOT resetting the reader byte to 0 here because we need
			// to re-use it on the next call. This is equivalent to the UnreadByte()
			// call in the other functions.

			// Reset the offset to start matching from the beginning.
			idx = 0

			continue
		}

		// There was no previous match. Write byte and reset.
		output.WriteByte(b[0])
		// Reset the reader byte to 0 so another byte will be read.
		b[0] = 0
	}
}

// io.Reader and io.Writer to model an infinite stream
// Provided by Bill Hathaway @billhathaway
func algorithmFive(r io.Reader, w *bytes.Buffer) {
	var idx int // where we are in the match
	var buf = make([]byte, 1)
	for {
		n, err := r.Read(buf)
		if err != nil || n == 0 {
			break
		}
		// does newest byte match next byte of find pattern?
		if buf[0] == find[idx] {
			idx++
			// if a full match, write out the replacement pattern
			if idx == len(find) {
				w.Write(repl)
				idx = 0
			}
			continue
		}
		// if we have matched anything earlier, write it
		if idx > 0 {
			w.Write(find[:idx])
			idx = 0
		}
		// match start of pattern?
		if buf[0] == find[0] {
			idx = 1
			continue
		}
		// write out what we read since no match
		w.Write(buf)
	}
	// write out any partial match before returning
	if idx > 0 {
		w.Write(find[:idx])
	}
}

// Functional version of algorithmSeven (replaceReader).
// Provided by Adam Williams @acw5
func algorithmSix(r io.Reader, w *bytes.Buffer) {
	buf := bufio.NewReaderSize(r, len(find))
	for {
		peek, err := buf.Peek(len(find))
		if err == nil && bytes.Equal(find, peek) {
			// A match was found. Advance the bufio reader past the match.
			if _, err := buf.Discard(len(find)); err != nil {
				return
			}
			w.Write(repl)
			continue
		}

		// Ignore any peek errors because we may not be able to peek
		// but still be able to read a byte.

		c, err := buf.ReadByte()
		if err != nil {
			return
		}
		w.WriteByte(c)
	}
}

// NewReplaceReader returns an io.Reader that reads from r, replacing
// any occurrence of old with new.
//
// algorithmSeven
//
// This is the io.Reader version of algorithmSix.
// Provided by Adam Williams @acw5
func NewReplaceReader(r io.Reader, old, new []byte) io.Reader {
	return &replaceReader{
		br:  bufio.NewReaderSize(r, len(old)),
		old: old,
		new: new,
	}
}

type replaceReader struct {
	br       *bufio.Reader
	old, new []byte
}

// Read reads into p the translated bytes.
func (r *replaceReader) Read(p []byte) (int, error) {
	var n int
	for {
		peek, err := r.br.Peek(len(r.old))
		if err == nil && bytes.Equal(r.old, peek) {
			// A match was found. Advance the bufio reader past the match.
			if _, err := r.br.Discard(len(r.old)); err != nil {
				return n, err
			}
			copy(p[n:], r.new)
			n += len(r.new)
			continue
		}

		// Ignore any peek errors because we may not be able to peek
		// but still be able to read a byte.

		p[n], err = r.br.ReadByte()
		if err != nil {
			return n, err
		}
		n++

		// Read reads up to len(p) bytes into p. Since we could potentially add
		// len(r.new) new bytes, we check here that p still has capacity.
		if n+len(r.new) >= len(p) {
			return n, nil
		}
	}
}

main_test.go

// All material is licensed under the Apache License Version 2.0, January 2004
// http://www.apache.org/licenses/LICENSE-2.0

// go test -run none -bench . -benchtime 3s -benchmem

// Tests to see how each algorithm compare.
package main

import (
	"bytes"
	"testing"
)

// assembleInputStream appends all the input slices together to allow for
// consistent testing across all benchmarks
func assembleInputStream() []byte {
	var out []byte
	for _, d := range data {
		out = append(out, d.input...)
	}
	return out
}

// Capture the time it takes to execute algorithm one.
func BenchmarkAlgorithmOne(b *testing.B) {
	var output bytes.Buffer
	in := assembleInputStream()

	for i := 0; i < b.N; i++ {
		output.Reset()
		algorithmOne(in, &output)
	}
}

// Capture the time it takes to execute algorithm two.
func BenchmarkAlgorithmTwo(b *testing.B) {
	var output bytes.Buffer
	in := assembleInputStream()

	for i := 0; i < b.N; i++ {
		output.Reset()
		algorithmTwo(in, &output)
	}
}

// Capture the time it takes to execute algorithm three.
func BenchmarkAlgorithmThree(b *testing.B) {
	var output bytes.Buffer
	in := bytes.NewReader(assembleInputStream())

	for i := 0; i < b.N; i++ {
		output.Reset()
		// Seek our reader to the beginning of the byte array
		in.Seek(0, 0)
		algorithmThree(in, &output)
	}
}

// Capture the time it takes to execute algorithm four.
func BenchmarkAlgorithmFour(b *testing.B) {
	var output bytes.Buffer
	in := bytes.NewReader(assembleInputStream())

	for i := 0; i < b.N; i++ {
		output.Reset()
		// Seek our reader to the beginning of the byte array
		in.Seek(0, 0)
		algorithmFour(in, &output)
	}
}

// Capture the time it takes to execute algorithm five.
func BenchmarkAlgorithmFive(b *testing.B) {
	var output bytes.Buffer
	in := bytes.NewReader(assembleInputStream())

	for i := 0; i < b.N; i++ {
		output.Reset()
		// Seek our reader to the beginning of the byte array
		in.Seek(0, 0)
		algorithmFive(in, &output)
	}
}

// Capture the time it takes to execute algorithm six.
func BenchmarkAlgorithmSix(b *testing.B) {
	var output bytes.Buffer
	in := bytes.NewReader(assembleInputStream())

	for i := 0; i < b.N; i++ {
		output.Reset()
		// Seek our reader to the beginning of the byte array
		in.Seek(0, 0)
		algorithmSix(in, &output)
	}
}

// Capture the time it takes to execute algorithm seven.
func BenchmarkAlgorithmSeven(b *testing.B) {
	var output bytes.Buffer
	in := bytes.NewReader(assembleInputStream())

	for i := 0; i < b.N; i++ {
		output.Reset()
		// Seek our reader to the beginning of the byte array
		in.Seek(0, 0)
		output.ReadFrom(NewReplaceReader(in, find, repl))
	}
}