Optimize implementation of "replace substrings after offset" utility function to

Optimize implementation of "replace substrings after offset" utility function to
be worst-case linear instead of quadratic.

BUG=277732
TEST=none

Committed: https://crrev.com/9504bdee450d72eecc7e981b46d14968dcfb9d01
Cr-Commit-Position: refs/heads/master@{#315942}

[Peter Kasting, 2015-02-12 02:12:24]

pkasting@chromium.org changed reviewers:
+ thestig@chromium.org

[Peter Kasting, 2015-02-12 02:12:24]

OWNERS roulette selects: thestig!  (Sorry.)

After implementing this and testing it, I don't know how much it will end up
speeding up pathological cases.  In my debug build, these changes made
right-clicking the omnibox with a ~250K character test string (which reaches
this code repeatedly) somewhat faster, dropping the max and average runtime of
this function by about 50% (would be less for shorter strings and more for
longer, and very dependent on the exact strings supplied).  Unfortunately this
appears to only be a fraction of the total time spent processing this input, so
the UI is still pretty unresponsive (see bug for more background of this case).

Still, since I got it all written, and it should always be at least as fast as
the old code if not faster, it seems like it's worth landing.

Yes, there are some existing unittests for this function (and they caught an
initial bug where I failed to account for >1-byte character string types).

[Lei Zhang, 2015-02-12 05:22:26]

lgtm

Fun facts:
- according to cs.chromium.org, there's only 1 non-test caller that passes in a
non-zero offset.
- nobody uses the string16 version with replace_all=false.

[Peter Kasting, 2015-02-12 06:51:35]

The CQ bit was checked by pkasting@chromium.org

[commit-bot: I haz the power, 2015-02-12 06:52:23]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/916133004/1

[commit-bot: I haz the power, 2015-02-12 06:55:46]

Committed patchset #1 (id:1)

[commit-bot: I haz the power, 2015-02-12 06:56:47]

Patchset 1 (id:??) landed as
https://crrev.com/9504bdee450d72eecc7e981b46d14968dcfb9d01
Cr-Commit-Position: refs/heads/master@{#315942}