Fast Algorithms for Exact String Matching | Hacker News Reader

Fast Algorithms for Exact String Matching

arxiv.org

44 pointsuser_23571110 comments

How is this better than a search on a suffix tree created with good old Ukkonen algorithm? https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

I'm going by the abstract here, but:

You'd build the suffix tree from the haystack, whereas their algorithm preprocesses the needle.

So I guess it mostly depends if you're going to be repeatedly searching different strings in the same document, or if you're searching for the same string in many different documents. Plus, space requirements might be relevant too, as a preprocessed haystack is probably bigger than a preprocessed needle.

Complete dupe: same URL and same submitter: user_235711.

https://news.ycombinator.com/item?id=10318008

We invited user_235711 to repost it. We've been trying this lately as an experiment in giving good submissions multiple cracks at the bat. However, from comments in the thread it sounds as if this article may not be as substantive as it looks.

(Also, don't forget that on HN a small number of reposts is ok if a story hasn't had significant attention yet: https://news.ycombinator.com/newsfaq.html. Otherwise what makes it off /newest is dominated by randomness.)

Are "we" are not powerful enough to just propel the original object to the front page, instead of requiring a freshly-minted replica?

This is the third time someone has asked me this since yesterday, so there's clearly a real question here, and maybe a solution that we haven't found yet.

We can help 'propel' things for a few hours, but after that the posts look weird on the front page, e.g. if they have say 3 points and are many hours old. Plus we want to be able to invite reposts for things that are much older. If we notice—or anyone points out—a years-old submission that was fabulous and went nowhere, let's give it another shot. That's not an uncommon case.

If anyone can suggest a better solution than "make a new post in append-only fashion" I'd love to hear it.

> If anyone can suggest a better solution than "make a new post in append-only fashion" I'd love to hear it.

Command tab category: "featured", where submissions are ordered in a way that certain "editor's choice" submissions are boosted.

This solves the problem of propelled posts looking "weird" on the front page; they look weird where that is the behavior.

"Featured" doesn't have to be ever-present; if there is nothing being featured at the moment, the link can disappear. Its intermittent manifestation could help get it noticed and used.

Not sure you know how the algorithms on reddit or hacker news work but typically they are a function of some combination of log(upvotes) and time. The log function (or some closely related function that hacker news may use) ensures that the first couple votes are the most crucial to bring submissions higher on the front page. That being said, the variance on these first votes are high and basically determine whether or not the submission will be successful. Date and time also greatly affect how popular an article will be. Thus the re-submissions.

It's okay to resubmit things that don't get attention.

But, this paper is really weird. The abstract makes no sense (from a readability perspective, it just dives right in). It's more of a brain dump from the creators than anything relevant to a wider audience. How about a concrete implementation somewhere instead of LaTeX psuedocode?

I agree with you on the readability pov. It's almost as if the author just wanted to publish something.

Reply on news.ycombinator.com