How many mesas begin with a given string?

Question

Let's call a non-empty list of strings a mesa if the following conditions hold:

1. Each listed string is non-empty and uses only characters that occur in the first string.
2. Each successive string is exactly one character longer than the preceding string.
3. No string in the list is a subsequence of any other string in the list.

The term "mesa" is from visualizing like this (where the xs are to be various characters):

    xx..x
    xx..xx
    xx..xxx
    .
    .
    .
    xx..xxx..x 

NB: It's a mathematical fact that only finitely many mesas begin with a given string. Note the distinction between subsequence vs. substring; e.g., 'anna' is a subsequence (but not a substring) of 'banana'.

Challenge:

• Write the shortest program that takes an arbitrary non-empty alphanumeric input string and outputs the number of mesas that begin with that string.

Input (stdin):

• Any non-empty alphanumeric string.

Output (stdout):

• The number of mesas that begin with the input string.

Scoring:

• The winner is the program with the least number of bytes.

Example mesas

Only one mesa starts with a:

a

Only one mesa starts with aa:

aa

Many mesas start with ab:

ab        ab        ab        ab        (and so on)
          baa       aaa       bbb
                    bbba      bbaa
                              baaaa
                              aaaaaa

Answer 1

GolfScript (106 103 chars)

n-..&1/:Z;]]0,\{.@+\{['']:E+.-2=,)E\{{`{+}+Z/}%}*{:x`{\1,+\{1$(@={\}*;}/0=!}+1$?!{.);[x]+\}*}/;}%.}do;,

Somewhere in the heart, of course, is some code from Is string X a subsequence of string Y?

Answer 2

Ruby, 142 characters

m=->l{[*l[0].chars].repeated_permutation(l[-1].size+1).reduce(1){|s,x|l.any?{|y|x*''=~/#{[*y.chars]*'.*'}/}?s:s+m[l+[x*'']]}}
p m[[gets.chop]]

This algorithm is constructive, i.e. it builds all possible mesas for the input string and counts them. It makes the program really, really slow - but hey, it is codegolf.

Example runs:

> a
1
> aa
1
> ab
43