MessageInABottle

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Recursion
{
    class MessageInABottle
    {
        static List<KeyValuePair<char, string>> ciphers = new List<KeyValuePair<char, string>>();
        static string message;

        public static void Main()
        {
            message = Console.ReadLine();
            string cipher = Console.ReadLine();

            char key = char.MinValue;
            StringBuilder value = new StringBuilder();

            for (int i = 0; i < cipher.Length; i++)
            {
                //if (char.IsLetter(chipher[i]))
                if (cipher[i] >= 'A' && cipher[i] <= 'Z')
                {
                    if (key != char.MinValue)
                    {
                        var pair = new KeyValuePair<char, string>(key, value.ToString());
                        ciphers.Add(pair);
                        value.Clear();
                    }
                    key = cipher[i];
                }
                else
                {
                    value.Append(cipher[i]);
                }
            }

            if (key != char.MinValue)
            {
                var pair = new KeyValuePair<char, string>(key, value.ToString());
                ciphers.Add(pair);
                value.Clear();
            }

            Solve(0, new StringBuilder());

            Console.WriteLine(solutions.Count);
            //solutions.Sort();
            foreach (var solution in solutions)
            {
                Console.WriteLine(solution);
            }
        }

        static SortedSet<string> solutions = new SortedSet<string>();

        static void Solve(int secretMsgIndex, StringBuilder sb)
        {
            if (secretMsgIndex == message.Length)
            {
                solutions.Add(sb.ToString());
                return;
            }

            foreach (var cipher in ciphers)
            {
                if (message.Substring(secretMsgIndex).StartsWith(cipher.Value))
                {
                    sb.Append(cipher.Key);
                    Solve(secretMsgIndex + cipher.Value.Length, sb);
                    //sb.Remove(sb.Length - 2, 1);
                    sb.Length--;
                }
            }
        }
    }
}