ABC287-E Karuta

問題へのリンク

C#のソース(辞書順にソートする方法)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("abc");
            WillReturn.Add("abb");
            WillReturn.Add("aac");
            //2
            //2
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("11");
            WillReturn.Add("abracadabra");
            WillReturn.Add("bracadabra");
            WillReturn.Add("racadabra");
            WillReturn.Add("acadabra");
            WillReturn.Add("cadabra");
            WillReturn.Add("adabra");
            WillReturn.Add("dabra");
            WillReturn.Add("abra");
            WillReturn.Add("bra");
            WillReturn.Add("ra");
            WillReturn.Add("a");
            //4
            //3
            //2
            //1
            //0
            //1
            //0
            //4
            //3
            //2
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        List<string> SList = InputList.Skip(1).ToList();
        SList.Sort();

        var AnswerDict = new Dictionary<string, int>();
        for (int I = 0; I <= SList.Count - 1; I++) {
            var AnswerKouho = new List<int>();
            if (0 < I) {
                AnswerKouho.Add(GetMatchCnt(SList[I - 1], SList[I]));
            }
            if (I < SList.Count - 1) {
                AnswerKouho.Add(GetMatchCnt(SList[I + 1], SList[I]));
            }
            AnswerDict[SList[I]] = AnswerKouho.Max();
        }

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1)) {
            sb.Append(AnswerDict[EachStr]);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    // 文字列2つを引数として、何文字一致するかを返す
    static int GetMatchCnt(string pStr1, string pStr2)
    {
        int WillReturn = 0;
        for (int I = 0; I <= pStr1.Length - 1; I++) {
            if (I > pStr2.Length - 1) break;

            if (pStr1[I] != pStr2[I]) {
                break;
            }
            WillReturn++;
        }
        return WillReturn;
    }
}

C#のソース(ローリングハッシュを使う方法)

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();
        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        var HashArrList = new List<decimal[]>();

        foreach (string EachStr in InputList.Skip(1)) {
            var InsRollingHash = new RollingHash(EachStr);
            HashArrList.Add(InsRollingHash.mHashArr);
        }

        var CntDict = new Dictionary<decimal, int>();
        foreach (decimal[] EachHashArr in HashArrList) {
            foreach (decimal EachHash in EachHashArr) {
                if (CntDict.ContainsKey(EachHash) == false) {
                    CntDict[EachHash] = 0;
                }
                CntDict[EachHash]++;
            }
        }

        var sb = new System.Text.StringBuilder();
        foreach (decimal[] EachHashArr in HashArrList) {
            int Answer = 0;
            foreach (decimal EachHash in EachHashArr) {
                if (CntDict[EachHash] == 1) {
                    break;
                }
                Answer++;
            }
            sb.Append(Answer);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}

#region RollingHash
// ローリングハッシュ
internal class RollingHash
{
    const decimal Base = 100M;
    const decimal Hou = 67280421310721M;

    // ハッシュ値[終了Ind]で、[0,終了Ind]のハッシュ値を保持
    internal decimal[] mHashArr;

    // 桁の重みの配列
    decimal[] mOmomiArr;

    // コンストラクタ
    internal RollingHash(string pTargetStr)
    {
        decimal Omomi = 1;
        long UB = pTargetStr.Length - 1;

        mHashArr = new decimal[UB + 1];
        mOmomiArr = new decimal[UB + 1];
        for (int I = 0; I <= UB; I++) {
            mOmomiArr[I] = Omomi;
            if (I > 0) {
                mHashArr[I] += mHashArr[I - 1] * Base;
                mHashArr[I] %= Hou;
            }
            mHashArr[I] += pTargetStr[I];
            mHashArr[I] %= Hou;
            Omomi *= Base;
            Omomi %= Hou;
        }
    }

    // [Sta,End]のハッシュ値を返す
    internal decimal GetRangeHash(long pSta, long pEnd)
    {
        decimal WillReturn = mHashArr[pEnd];
        if (pSta > 0) {
            long Range = pEnd - pSta + 1;
            decimal PrevVal = mHashArr[pSta - 1];
            decimal MinusVal = PrevVal * mOmomiArr[Range];
            MinusVal %= Hou;
            WillReturn -= MinusVal;
            if (WillReturn < 0) {
                WillReturn += Hou;
            }
        }
        return WillReturn;
    }
}
#endregion

解説

英和辞典とか氏名でのソートをイメージすると
辞書順にソートしての前後が解候補だと分かります。

ローリングハッシュを使って解くこともできます。