A variant of this algorithm is what glibc uses for its implementation of memmem. I say "variant" because it uses a shift table in some cases.
I found this original paper describing the algorithm to be notable, in particular for how rigorous it is. I've read it a couple of times so far, but I still don't grok everything. One thing I'm particularly interested in is trying to simplify the algorithm so that you don't need to handle the short and long period cases differently. In particular, the paper hints that this is possible:
> The string-matching algorithm of Section 2 uses the period of
the pattern. A previous computation of this period is possible.
This precomputation can be made easily by using Knuth, Morris,
and Pratt’s algorithm on the pattern. This precomputation,
combined with both the computation of a critical factorization
of the pattern and our string-matching algorithm, leads to an
algorithm that is globally linear in time and space. But, since
the string-matching algorithm operates in constant space, it
is desirable to improve on the precomputation of the period
of the pattern, with the aim of obtaining a global algorithm
that is in linear time and constant space. There are two ways
to achieve that goal. One is a direct computation of the
period by an algorithm operating in linear time and constant
space. Such an algorithm is described in . It can also be
obtained as a consequence of the results in . Our approach
here is different. We shall describe a modification of our
string-matching algorithm that avoids the use of the period of
the pattern, giving an algorithm that is linear time and constant
space on the whole. The point is that the exact value of the
period of the pattern is actually needed only when it is less
than half the length of the pattern. When the period of the
pattern is larger, an even simpler string-matching algorithm is
But they don't seem to explain why they went the route of approximating the period even when they cite algorithms that satisfy their desired complexity constraints (linear time, constant space). So my next task is to read the cited papers and hopefully discern for myself.
Very good stuff, I learned about the duality between borders and periods and I understand how the KMP algorithm requires O(m) (pattern length) space to construct the table, but the critical factorization only takes up 2 integers O(1) so it's a much more space efficient matching algorithm.
A "save to favorites" or "bookmark" feature, separate from the list that's generated by your upvote history, and longer term, the ability to organize them. Sometimes it's hard to go back and find things, and it would be cool to have the ability to organize research, etc. :)
This was a big problem for me on various forums. I don't want one aggregator to control this on all sites I use either. I ended up keeping per-site folders with text copies of the good stuff with links back to originals. Each site letting one organize the material is a step up. API's that make that easy to automate might be next step up from there. Then, what goes into each site can be locally generated, customized for each per their style, and uploaded.
I don't want one aggregator to control this on all sites I use either.
Definitely! This was partly the motivation for starting the site. Your bookmarks are yours, and it's important to us to avoid siloing data. The API might end up similar to https://github.com/HackerNews/API.
re UFO's. I've seen two. One was, after interviewing pilots, a plane with unusual lighting at a weird angle. The other didn't matching anything I've ever seen or read about with shape and movement that were impossible. I kept interviewing pilots, what few I met. All of them claimed to have seen one, which all looked different, with behavior making them think same thing. They'd all say they screwed with the planes, too. Get close, far away, do nothing for a while, shoot off, do angles/rates with enough G's to kill, and so on. The only thing I can't eliminate is fact that many pilots have an insider culture plus a sense of humor that involves messing with people. It's actually possible those statements are a running joke among most of them on the rest of us. Leaning more in the other direction, though. I just have too little data to know what that means.
Now, far as wild programs government funded, I have two favorites with the evil one first. Blue Peacock, if it was real, just goes to show how much drugs people were doing at the time. Although they gripe about millennials, they aren't trying to plant friggin, nuclear, land mines in the ground while torturing and wasting perfectly good chickens.
The other one, which was implemented for a while, was remote viewers in programs like Operation Stargate. That got lots of internal attention. Even better, they made a hilarious, fictional movie that included quite a bit of real stuff from the program like the guy who tried to run through walls and the goat tests. Yall probably enjoy it. :)