[BUG] Poor performance scaling of str.count with long strings

[GregoryKimball]

Describe the bug
During large string testing, I noticed that we have poor performance scaling of the str.count API with string length.

Steps/Code to reproduce bug

df = cudf.DataFrame({'a':['abc','cdf']})
for n in [1,10,100,1000, 10000]:
    df['b'] = df['a'].str.repeat(n)
    t0 = time.time()
    _ = df['b'].str.count('a')
    t1 = time.time()
    string_length = int(df['b'].str.len().mean())
    print(f'count on string len {string_length}, took {t1-t0} seconds')

count on string len 3, took 0.0012462139129638672 seconds
count on string len 30, took 0.00027561187744140625 seconds
count on string len 300, took 0.0019071102142333984 seconds
count on string len 3000, took 0.12342023849487305 seconds
count on string len 30000, took 11.811477422714233 seconds

Expected behavior
The observed scaling is something like O(n^2), but I would expect scaling more like O(n).

Additional context
This issue is one component of improving performance with long strings in #13048

[davidwendt]

This is a character count and not the number of bytes so resolving multi-byte characters requires some computation.
Regardless, it should be possible to compute the character count in a more parallel way for long strings.

Thought this was a call to cudf::strings::character_count() when it is actually a call to cudf::strings::count_re() which is a regex call.

https://docs.rapids.ai/api/cudf/stable/user_guide/api_docs/api/cudf.core.column.string.stringmethods.count/#cudf.core.column.string.StringMethods.count

Regex calls like this one will be difficult to make scale well for long strings as mentioned in #13048