連続しない部分文字列の数え上げ

内容

文字列が与えられるから、連続しない部分文字列(*1)は何個あるか数え上げたい。
ただし、部分文字列の内容が同じであれば重複して数え上げてはいけない。

(*1)
連続しない部分文字列とは（自分で勝手に名付けたんだけど・・）、
以下のように、連続しない文字を選んでもいいやり方でとった部分文字列のこと。

元の文字列：Eakabgizxngge
選ぶ文字　：^ ^^  ^  ^ ^  ⇔飛び飛びで連続してない！
出来る部分文字列：Ekaing

解法

i番目の文字を"使って"部分文字列を作った時に、何個出来るのかを考えてみる。
0番目～i-1番目の文字については、数え上げは出来ているとする。
以下を見て欲しい。
index 8番目の文字を"使って"部分文字列が何個できるか考えている状況である。
また、0～7番目の文字を使った時の部分文字列の数はすでに判明している。

ここで、末尾がaのもの(緑)、末尾がbのもの(黄)、末尾がcのもの(青)を使用したとき、それぞれ重複せずに数え上げられる。
xxxxaa、xxxxba、xxxxcaとなり、内容が違う部分文字列になるからね。

では、末尾が同じもの同士は数え上げるにあたってどうしたらよいかというと、今考えている場所から直近のものだけを使い、それ以外のものは無視するのが良い。
例えば図でいうとindex5と6は同じaである。で、index6の部分文字列の数40は、index5の部分文字列を考慮して算出されたものであり完全に含めているため、index6を数を足し合わせれば、index5の数はいらなくなる。index3と7も同じことが言える。
よって、iのパターン数はindex4, 6, 7を足し合わせた数となる。

また、0～i-1番目の文字を全く使用せず、i番目の文字のみを使用する場合として、1を追加すれば、晴れて「i番目の文字を"使って"部分文字列を作った時に、何個出来るのか」の数え上げは完了である。
(図でいうならば、index8の場合、20 + 40 + 50 + 1 = 111となる)

ソースコード

string s;
long long memo[100];

int main() {

    string input = "aaba";

    s = input;

    memset(memo, 0, sizeof(memo));
    long long output = f(s.size());

    cout << "output : " << output << endl;

    return 0;
}

// i番目までの文字を使用し、i番目の文字を"使った"時の部分文字列の場合の数
long long f(int i) {
    if (i == 0) {
        // 最初の文字の場合
        // 最初の文字を使うのは１パターンだけ
        return 1;
    } else {
        // 最初の文字以外の場合

        // メモ
        long long &res = memo[i];

        if (res == 0) {
            // メモがない場合

            // 左最寄りの各文字でのパターンを足しこんでいく
            for (int j = 0; j < 26; j++) {
                char ch = j + 'a';
                // 左最寄りの文字chのインデックスを見つける
                int pi = find_prev(i, ch);
                if (pi != -1) {
                    // 見つかったら再帰でパターン数を取得して足しこむ
                    res += f(pi);
                }
            }

            // i番目の文字だけを使う場合の１パターンを足す
            res++;
        }

        return res;
    }
}

// baseより左で最も近い文字chのインデックスを探す
int find_prev(int base, char ch) {
    for (int i = base - 1; i >= 0; i--) {
        if (s[i] == ch) return i;
    }
    return -1;
}