Timeline for Deciding if a wildcard string is completely matched by another wildcard string in a set
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2011 at 11:30 | history | tweeted | twitter.com/#!/StackCSTheory/status/62478705078972416 | ||
| Apr 15, 2011 at 15:49 | vote | accept | Christopher Monsanto | ||
| Apr 13, 2011 at 14:51 | answer | added | ShyPerson | timeline score: 3 | |
| Apr 11, 2011 at 17:05 | history | edited | Christopher Monsanto | CC BY-SA 3.0 |
added 97 characters in body
|
| Apr 11, 2011 at 16:56 | history | edited | Christopher Monsanto | CC BY-SA 3.0 |
added 49 characters in body
|
| Apr 11, 2011 at 6:02 | comment | added | Christopher Monsanto | My above comment probably isn't helpful for a complexity argument :(. There isn't really any relation between the size of the strings and the size of the set, if you allow the size of the strings to vary as well. If that is true about being $O(n)$ worst case that is unfortunate, but, I am much more interested in the average-case (or approximations) anyway. | |
| Apr 11, 2011 at 5:52 | comment | added | Christopher Monsanto | Sorry if I wasn't clear. The strings have $O(1)$ size; for all intents and purposes, you can think of them as being 32 characters long. "String" was just a convenient abstraction for framing the problem -- they are actually represented as (integer, bitmask) tuples, so that I can calculate the join and $v \leq w$ in only a few machine operations. (Of course, the problem can be naturally extended to larger constant size strings by increasing the number of integer and bitmask fields). | |
| Apr 11, 2011 at 5:35 | comment | added | Artem Kaznatcheev♦ | how large are the strings allowed to be? And why are you not accounting for their length in the complexity? Obviously you need the strings to be $\Omega(log n)$ otherwise you just wouldn't have $n$ distinct strings to work with. It also seems intuitive that if you allow $O(n)$-length strings, then you will have to look at all your strings in your data structure in the worst case... are there any bounds on the string length? Poly-logarithmic? $o(n)$? | |
| Apr 11, 2011 at 4:17 | history | asked | Christopher Monsanto | CC BY-SA 3.0 |