Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there research that applies to classical questions of stringology; maximal repetitions, pattern matching, longest repeated substring, .. but replaced the definition of string as a sequence of elements of an alphabet with a sequence of subsets of an alphabet?

My requirement is a softer definition for "x is substring of y" that works on the subset relation instead of equivalence between elements of the sequence.

To give examples ("," is the seperator between sets):

  • "$a,a,a$" is a substring of "$abcd,axyz,artz$".
  • In "$a,b,a,a,c,a$" "$a,,a$" is the most common substring of length 3 ("$a,,,a$" of length 4).

(I am kinda uncomfortable using/inventing the words setstring, subsetstring, uh setstringsubset Oo.. in the expectation that someone must have had that idea before me)

share|cite|improve this question
There is no difference. Just replace the alphabet $\Sigma$, by your new alphabet $\mathscr P(\Sigma)$, the powerset. – martini Oct 4 '12 at 11:43
Oh, I'm sorry. I think I wasn't explicit, I edited the question. I am rather certain that (at least for the research I found) the results can not be copied over with that substring notion in mind. – SimonS Oct 7 '12 at 18:59
I do not understand what you mean, really. Your ebaloration did not help :-/ – Mariano Suárez-Alvarez Oct 7 '12 at 19:08
I probably should just say what I need it for then. I needed results of the type: Given a sequence of sets of length n with an alphabet of size a, what are the highest/average number of different subset strings possible. (and try again with the question^^) – SimonS Oct 7 '12 at 19:19
I mean trying again with editing my question, I mean that! phew – SimonS Oct 7 '12 at 19:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.