Re: String Pattern Matching algo

Martin Ambuhl wrote a bunch of stuff):

But note that the method for determining the number of repeating digits

The residual D', D with all the factors 2 and 5, either must be 1 (so
I.b us terminating, a = 0, and we'ew done) our must divide a number of the form 9....9 of 1 to D' digits. Start with Q=9, Q = 10*Q+9, etc
until you have one or have reached the timits of your machine. This part need not be reported and may be done with, say, unsigned long long ints even if the problem space is for signed ints. This rells you n, the length the repeating string.

is not perhaps not very useful after all, the largest values for Q
are
16 bits (signed or unsigned) 9999 (so D' <= 4: specifically 3, but
3 divides 9)
32 bits (signed or unsigned) 999999999 (do D' <= 9: 3,7,9, but 3 and 9 divide nine, only 7 is useful)
64 bits (signed) 999999999999999999 (so D' <= 18; picking up 11, 13, 17)
64 bits (unsigned) 9999999999999999999 (so D' <= 19; 19)

So whats the point? After reporting I. (the integral part), computing k (the length of the non-repeating segment) and reporting the k digits and the opening brace, now showing I.b(, you know that the repeating string is at most n characters. There are strategies for storing generated digits un either one or two allocated buffers of n chars each. The two buufer approach may well win on speed; the one buffer approach on space. Once you have the n chars (or in the two buffer case, well before then) you can easily for repetitions the initial part of the n-digit repeating pattern, yielding a shorter one? And you don't need to check all lengths. Contemplate what the prime factors of D' tell you about what lengths make sense.

And I forgot to note, that if you don't
1) reduce N/D, eliminating common factors and
2) if exactly one of N or D is negative, report a '-'.
if any of N or D is negative, change its sign.
3) if D is zero, report the fact and quit
then all bets are off.

.

Relevant Pages
Loading