Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: skip: an O(n/m) pattern recognition algorithm |
| Date | 2021-07-30 22:45 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87im0rlbln.fsf@bsb.me.uk> (permalink) |
| References | <37b5e9bf-fa94-4a77-9c33-7bb14611186dn@googlegroups.com> <38d87cc6-ec27-4001-b4e9-23f6390a47a4n@googlegroups.com> <eab3cf40-2124-43e8-a617-a576ee669a2fn@googlegroups.com> <871r7f29kb.fsf@bsb.me.uk> <dd14078f-5bfe-4d1a-90fd-9b3f3a966fa9n@googlegroups.com> |
Daniel Pehoushek <pehoushek1@gmail.com> writes: > On Friday, July 30, 2021 at 9:52:22 AM UTC-4, Ben Bacarisse wrote: >> Daniel Pehoushek <pehou...@gmail.com> writes: >> >> > anyone interested in sublinear pattern matching? >> Post something about it. >> > O(n/m) is a giant leap from O(n+m)... >> I think you have something wrong there. The formal meaning of big O is >> not 100% obvious when the function is of more than one variable, so >> maybe you are using the notation in a slightly odd way? > > no, i really do mean sublinear, n/m. > obviously growing in efficiency as m grows and n remains large. What is the asymptotic cost of matching a pattern of length n in a string of length n? Does the complexity depend on whether the match succeeds or fails? Have you got an actual formula for the number of step the algorithm takes for patterns of length m in strings of length n? An actual formula would about the complexity of multi-variable Big O notation. Is the algorithm published? -- Ben.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-27 15:40 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-29 01:19 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 05:43 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 05:55 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 06:28 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 06:40 -0700
Re: skip: an O(n/m) pattern recognition algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 14:52 +0100
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 14:10 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 14:15 -0700
Re: skip: an O(n/m) pattern recognition algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 22:45 +0100
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 13:30 -0700
Re: skip: an O(n/m) pattern recognition algorithm Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-30 15:14 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-07-30 19:11 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 21:49 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 21:55 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 22:10 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 22:27 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 23:00 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-02 23:09 -0700
Re: skip: an O(n/m) pattern recognition algorithm Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-08-03 00:20 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 00:48 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 00:51 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 00:56 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:05 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:18 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:31 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:41 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 01:58 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 02:16 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 02:30 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 02:45 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 03:15 -0700
Re: skip: an O(n/m) pattern recognition algorithm Andy Walker <anw@cuboid.co.uk> - 2021-08-03 11:44 +0100
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 04:04 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 04:34 -0700
Re: skip: an O(n/m) pattern recognition algorithm Andy Walker <anw@cuboid.co.uk> - 2021-08-03 16:56 +0100
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 11:25 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-03 13:16 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 00:51 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:18 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:27 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:34 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:40 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:46 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 01:51 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 02:15 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 02:29 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 02:48 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 03:22 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 03:50 -0700
Re: skip: an O(n/m) pattern recognition algorithm "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-08-04 12:47 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 12:59 -0700
Re: skip: an O(n/m) pattern recognition algorithm Daniel Pehoushek <pehoushek1@gmail.com> - 2021-08-04 13:47 -0700
csiph-web