Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - unique substrings

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    56

    unique substrings

    Hi,

    well my question is: Is the following problem trivial enough not to be proved and if not then would you suggest proveing it by cases or induction.


    Problem

    let $S$ be a string and |$S$| its size. Let $S[i,i+k-1]$ be a substring of S. Let $\Sigma$ be the alphabet and |$\Sigma|$ its size. Let $k \in Z^{+}$. Then $\forall |S| \in Z{+}, |\{S[i,i+k-1] : S[i,i+k-1] \neq S[j,j+k-1], \wedge i,j\in[1,|S|-k+1] \wedge i\neq j\}| \leq |\Sigma|^{k}$


    so waht i want to prove is that no matter how large the string is the number of different k size substrings cannot be larger then the number of possible k size substrings. To me this looks obvious enough to be assumed. but if think it is not then would you proceede by proving cases <,>,= or ....?


    thnx

    b
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: unique substrings

    If there were more distinct $k$-size substrings than possible $k$-size substrings, then at least one of these strings is impossible.

    Impossibru!

    YES! You can assume that!

    I'm assuming by "different" you mean "distinct", so for example if S = AABAB, we have two strings S[2,3] and S[4,5] which are "different substrings" but not "distinct" since both are AB.

    I think you'll be stuck with that as a rather coarse upper bound, because how strings might be duplicated (via letter repetition) is going to get very computationally difficult as the size of your alphabet goes up.
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: unique substrings

    The total number of size- k substrings of string S is \max\{|S|-k+1,0\}. So,

    \forall |S|\in \Bbb{Z}^+, |\{S[i,i+k-1]: 1\le i\le |S|-k+1 \text{ and }\forall j\in \Bbb{Z}^+ \text{ s.t. }1\le i\le j \le |S|-k+1, S[i,i+k-1] = S[j,j+k-1]\text{ iff }i=j\}| \le \max\{|S|-k+1,0\}

    (This is another way to write the set of all distinct size- k substrings of the string S).

    The point being, if |S|-k+1 is small in comparison to |\Sigma|^k, then |S|-k+1 is a far better upper bound.
    Last edited by SlipEternal; June 11th 2014 at 12:49 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: unique substrings

    Quote Originally Posted by SlipEternal View Post
    The total number of size- k substrings of string S is \max\{|S|-k+1,0\}. So,

    \forall |S|\in \Bbb{Z}^+, |\{S[i,i+k-1]: 1\le i\le |S|-k+1 \text{ and }\forall j\in \Bbb{Z}^+ \text{ s.t. }1\le i\le j \le |S|-k+1, S[i,i+k-1] = S[j,j+k-1]\text{ iff }i=j\}| \le \max\{|S|-k+1,0\}

    (This is another way to write the set of all distinct size- k substrings of the string S).

    The point being, if |S|-k+1 is small in comparison to |\Sigma|^k, then |S|-k+1 is a far better upper bound.
    Especially if by "substring" we mean that sequence and adjacency are preserved (no scrambling or skipping of letters). Indeed, |S| is going to be the controlling factor (longer strings yield more substrings, if $k < |S|$ is fixed).

    I do want to point out that counting the "distinct" substrings, as opposed to "any" substrings, is still quite complicated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many unique objects...
    Posted in the Statistics Forum
    Replies: 6
    Last Post: February 18th 2014, 08:02 AM
  2. Replies: 4
    Last Post: November 14th 2013, 09:39 AM
  3. Inverses are unique
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 28th 2011, 11:36 AM
  4. Unique identity
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 7th 2010, 02:10 PM
  5. Unique Proportions?
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: October 13th 2009, 07:27 PM

Search Tags


/mathhelpforum @mathhelpforum