```Move DeBruijnString() alongside StringGenerator.

Change-Id: Id7e2ed4be60611c0a4e56c621d9449a595c94c5e
```
```diff --git a/re2/testing/dfa_test.cc b/re2/testing/dfa_test.cc
index 9d8b533..9e15a41 100644
--- a/re2/testing/dfa_test.cc
+++ b/re2/testing/dfa_test.cc
```
```@@ -122,44 +122,6 @@
re->Decref();
}

-// Generates and returns a string over binary alphabet {0,1} that contains
-// all possible binary sequences of length n as subsequences.  The obvious
-// brute force method would generate a string of length n * 2^n, but this
-// generates a string of length n + 2^n - 1 called a De Bruijn cycle.
-// See Knuth, The Art of Computer Programming, Vol 2, Exercise 3.2.2 #17.
-// Such a string is useful for testing a DFA.  If you have a DFA
-// where distinct last n bytes implies distinct states, then running on a
-// DeBruijn string causes the DFA to need to create a new state at every
-// position in the input, never reusing any states until it gets to the
-// end of the string.  This is the worst possible case for DFA execution.
-static std::string DeBruijnString(int n) {
-  CHECK_LT(n, static_cast<int>(8*sizeof(int)));
-  CHECK_GT(n, 0);
-
-  std::vector<bool> did(size_t{1}<<n);
-  for (int i = 0; i < 1<<n; i++)
-    did[i] = false;
-
-  std::string s;
-  for (int i = 0; i < n-1; i++)
-    s.append("0");
-  int bits = 0;
-  int mask = (1<<n) - 1;
-  for (int i = 0; i < (1<<n); i++) {
-    bits <<= 1;
-    bits &= mask;
-    if (!did[bits|1]) {
-      bits |= 1;
-      s.append("1");
-    } else {
-      s.append("0");
-    }
-    CHECK(!did[bits]);
-    did[bits] = true;
-  }
-  return s;
-}
-
// Test that the DFA gets the right result even if it runs
// out of memory during a search.  The regular expression
// 0[01]{n}\$ matches a binary string of 0s and 1s only if
```
```diff --git a/re2/testing/regexp_benchmark.cc b/re2/testing/regexp_benchmark.cc
--- a/re2/testing/regexp_benchmark.cc
+++ b/re2/testing/regexp_benchmark.cc
```
```@@ -792,40 +792,6 @@

/*
TODO(rsc): Make this work again.
-
-// Generates and returns a string over binary alphabet {0,1} that contains
-// all possible binary sequences of length n as subsequences.  The obvious
-// brute force method would generate a string of length n * 2^n, but this
-// generates a string of length n + 2^n - 1 called a De Bruijn cycle.
-// See Knuth, The Art of Computer Programming, Vol 2, Exercise 3.2.2 #17.
-static std::string DeBruijnString(int n) {
-  CHECK_LT(n, 8*sizeof(int));
-  CHECK_GT(n, 0);
-
-  std::vector<bool> did(1<<n);
-  for (int i = 0; i < 1<<n; i++)
-    did[i] = false;
-
-  std::string s;
-  for (int i = 0; i < n-1; i++)
-    s.append("0");
-  int bits = 0;
-  int mask = (1<<n) - 1;
-  for (int i = 0; i < (1<<n); i++) {
-    bits <<= 1;
-    bits &= mask;
-    if (!did[bits|1]) {
-      bits |= 1;
-      s.append("1");
-    } else {
-      s.append("0");
-    }
-    CHECK(!did[bits]);
-    did[bits] = true;
-  }
-  return s;
-}
-
void CacheFill(int iters, int n, SearchImpl *srch) {
std::string s = DeBruijnString(n+1);
std::string t;
```
```diff --git a/re2/testing/string_generator.cc b/re2/testing/string_generator.cc
index 030cc45..44837fe 100644
--- a/re2/testing/string_generator.cc
+++ b/re2/testing/string_generator.cc
```
```@@ -111,4 +111,31 @@
hasnext_ = true;
}

+std::string DeBruijnString(int n) {
+  CHECK_GE(n, 1);
+  CHECK_LE(n, 29);
+  const size_t size = size_t{1} << static_cast<size_t>(n);
+  const size_t mask = size - 1;
+  std::vector<bool> did(size, false);
+  std::string s;
+  s.reserve(static_cast<size_t>(n) + size);
+  for (size_t i = 0; i < static_cast<size_t>(n - 1); i++)
+    s += '0';
+  size_t bits = 0;
+  for (size_t i = 0; i < size; i++) {
+    bits <<= 1;
+    bits &= mask;
+    if (!did[bits | 1]) {
+      bits |= 1;
+      s += '1';
+    } else {
+      s += '0';
+    }
+    CHECK(!did[bits]);
+    did[bits] = true;
+  }
+  CHECK_EQ(s.size(), static_cast<size_t>(n - 1) + size);
+  return s;
+}
+
}  // namespace re2
```
```diff --git a/re2/testing/string_generator.h b/re2/testing/string_generator.h
index 6184176..73fbb51 100644
--- a/re2/testing/string_generator.h
+++ b/re2/testing/string_generator.h
```
```@@ -58,6 +58,19 @@
StringGenerator& operator=(const StringGenerator&) = delete;
};

+// Generates and returns a string over binary alphabet {0,1} that contains
+// all possible binary sequences of length n as subsequences.  The obvious
+// brute force method would generate a string of length n * 2^n, but this
+// generates a string of length n-1 + 2^n called a De Bruijn cycle.
+// See Knuth, The Art of Computer Programming, Vol 2, Exercise 3.2.2 #17.
+//
+// Such a string is useful for testing a DFA.  If you have a DFA
+// where distinct last n bytes implies distinct states, then running on a
+// DeBruijn string causes the DFA to need to create a new state at every
+// position in the input, never reusing any states until it gets to the
+// end of the string.  This is the worst possible case for DFA execution.
+std::string DeBruijnString(int n);
+
}  // namespace re2

#endif  // RE2_TESTING_STRING_GENERATOR_H_
```