graffe
  • Member for 11 years, 3 months
  • Last seen this week
n-dimensional pattern matching
Accepted answer
13 votes

You can solve the problem in a fixed number of dimensions by extending the linear time original solution of Bird from 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (...

View answer
How is Real-Time Computing defined?
11 votes

Like many things in life, there is no one definitive definition. For an algorithm to run in real-time, some people on the theoretical side say that this means it will take constant time per 'something....

View answer
Which model of computation is "the best"?
11 votes

There is no one totally satisfactory computational model in which to analyse algorithms sadly, even in what one might consider a traditional setting. That is assuming all data is readily accessible ...

View answer
Algorithm: Find the first k longest substrings between two similar strings
Accepted answer
4 votes

Depending on your application (and assuming I have correctly understood your general aim), a standard practical method will be to find all maximal repeated substrings between the two strings, number ...

View answer
Convolution without FFT
Accepted answer
2 votes

Take a look at Toom-Cook multiplication and see if that is helpful for what you need. The complexity is $O(n^{1+\epsilon})$ for any fixed $\epsilon>0$.

View answer
Matching substrings within two strings
2 votes

The answer is no. To find the full dictionary of maximal repeated substrings in linear time is a hard problem if no one has ever introduced you to a suffix tree or equivalent. However, if you don't ...

View answer
Mathematical background needed for pursuing a PhD in TCS
2 votes

Although a full answer may require knowing more about your situation and what you plan to research, you can't go too far wrong with some of the standard resources. Fundamentally you need to be ...

View answer