第2回PAST D パターンマッチ

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("ab");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("aa");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("aabbaabb");
            //33
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal string Pattern;
    }

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

        char[] DistinctCharArr = S.Distinct().ToArray();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.Pattern = "";
        Stk.Push(WillPush);

        var PatternList = new List<string>();
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (Popped.Level >= 1) {
                PatternList.Add(Popped.Pattern);
                if (Popped.Level == 3) {
                    continue;
                }
            }

            WillPush.Level = Popped.Level + 1;
            for (int I = 0; I <= DistinctCharArr.GetUpperBound(0); I++) {
                WillPush.Pattern = Popped.Pattern + DistinctCharArr[I].ToString();
                Stk.Push(WillPush);
            }
            WillPush.Pattern = Popped.Pattern + ".";
            Stk.Push(WillPush);
        }
        int Answer = PatternList.Count(pX => Regex.IsMatch(S, pX));
        Console.WriteLine(Answer);
    }
}

解説

正規表現のパターンを全探索してます。