Messages In A Bottle

using System;
using System.Collections.Generic;

class MessagesInABottle
{
  static void Main()
  {
    string message = Console.ReadLine(),
           cipher = Console.ReadLine();
    Dictionary<string, char> cipherParts = new Dictionary<string, char>();

    char currentLetter = '.';
    string currentDigit = "";
    foreach (char symbol in cipher)
    {
      if (char.IsLetter(symbol))
      {
        if (currentDigit != "")
        {
          cipherParts.Add(currentDigit, currentLetter);
          currentDigit = "";
        }
        currentLetter = symbol;
      }
      if (char.IsDigit(symbol))
      {
        currentDigit += symbol;
      }
    }
    if (currentDigit != "")
    {
      cipherParts.Add(currentDigit, currentLetter);
    }

    List<string[,]> decodedRemaining= new List<string[,]>(); // 0 for decoded, 1 for remaining
    string[,] initialState = new string [1,2];
    initialState[0, 0] = "";
    initialState[0, 1] = message;
    decodedRemaining.Add(initialState);
    List<string> results = new List<string>();
    int index=0;
    while (index < decodedRemaining.Count)
    {

      string[,] currentState = decodedRemaining[index];

      foreach (var element in cipherParts.Keys)
      {

        if (currentState[0, 1].StartsWith(element))
        {
          char letterToAdd;
          cipherParts.TryGetValue(element, out letterToAdd);

          string[,] decodingInProgress = new string[1, 2];
          decodingInProgress[0, 0] = currentState[0, 0] + letterToAdd.ToString();

          decodingInProgress[0, 1] = currentState.GetValue(0, 1).ToString().Substring(element.Length);
          if (decodingInProgress[0, 1] == "")
          {
            results.Add(decodingInProgress[0,0]);
          }
          else
          {
            decodedRemaining.Add(decodingInProgress);
          }
        }
      }

      index++;
      //decodedRemaining.RemoveAt(index-1);
    }

    results.Sort();
    //Print result
    Console.WriteLine(results.Count);
    for (int i = 0; i < results.Count; i++)
    {
      Console.WriteLine(results[i]);
    }
  }
}