Currently it's implemented very simply way to detect password reuse in PasswordReuseDetector. Namely each suffix of an input string is searched in map<string,>. Of course it's possible to implement it more effective with some kind of suffix tree or suffix array. But since this is the first implementation, it's easy to keep it as simple as possible for now.

This bug is created in order to optimize implementation in future.
 

https://codereview.chromium.org/2525593002/ is introducing a class PasswordReuseDetector. This class has a method CheckReuse(const base::string16& input, ...) and a data-member map |passwords_| keyed with string16. CheckReuse needs to find out whether some suffix of |input| is a key in |passwords_|.

Currently, the method does so by iterating over possible suffixes of |input| and using find() on the map. This makes O(m*n*log(n)) string comparisons for m being the length of |input| and |n| the size of |passwords_|. In addition to it, it also contains O(m) string copies and allocations which are not necessary. This approach was chosen in the initial code for its simplicity, to make review of the code easier.

However, there are more efficient solutions, for example:

Initialisation:
Instead of making |passwords_| a std::map, make it a std::vector of key-value pairs. Use the reverse of passwords as keys, and std::sort the vector.

Lookup:
Reverse also |input|. Now the task is to see if a prefix (of size at least kMinPasswordLengthToCheck) is a key in |passwords_|. This can be done via std::binary_search, using a custom comparator like this:
bool IsLongInputPrefix(const base::string16& str) {
  return /* whether str is a prefix of input of length at least
            kMinPasswordLengthToCheck */;
}

bool Compare(const base::string16& a, const base::string16& b) {
  if (IsLongInputPrefix(a) && IsLongInputPrefix(b))
    return false;
  return a < b;
}
(That comparator represents the preorder on strings obtained from the lexicographical order by glueing all long prefixes of input into a single equivalence class.)

This solution would need O(n*log(n)) comparisons for the initialisation, and O(log(n)) for the lookup.