No.52 よくある文字列の問題

■■■問題■■■

文字列Sが与えられる。
文字列Sの「先頭」または「末尾」から1文字ずつ文字をとってきて、
取った文字列とは別に、取った文字を順番につなげて新たに文字列を作る。
Sは、文字を取った後の文字列を新たなSとしてSの文字列がなくなるまで繰り返す。

この時、新たにできる文字列は何通りの文字列ができるか？

■■■入力■■■

S

Sは小文字のaからzのアルファベットからなる最短1文字最長10文字の文字列

■■■出力■■■

できる文字列の数Ansを出力せよ。
最後に改行を忘れないように。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("abc");
            //4
            //abc、acb、cab、cbaの4通りがある
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("aab");
            //3
            //aab、aba、baaの3通りがある
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("aaaaaaaaaa");
            //1
            //どのようにしてもaaaaaaaaaaにしかならない
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
        internal string CreateStr;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrStr = S;
        WillPush.CreateStr = "";
        stk.Push(WillPush);

        var CreateStrSet = new HashSet<string>();

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.CurrStr == "") {
                CreateStrSet.Add(Popped.CreateStr);
                continue;
            }

            Action<int> PushSyori = pRemoveInd =>
            {
                WillPush.CurrStr = Popped.CurrStr.Remove(pRemoveInd, 1);
                WillPush.CreateStr = Popped.CreateStr + Popped.CurrStr[pRemoveInd];
                stk.Push(WillPush);
            };

            PushSyori(0);
            PushSyori(Popped.CurrStr.Length - 1);
        }
        Console.WriteLine(CreateStrSet.Count);
    }
}

解説

深さ優先探索で全探索してます。