結果

問題 No.430 文字列検索
ユーザー aketijyuuzouaketijyuuzou
提出日時 2024-10-10 20:49:00
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 297 ms / 2,000 ms
コード長 4,185 bytes
コンパイル時間 7,909 ms
コンパイル使用メモリ 166,780 KB
実行使用メモリ 188,284 KB
最終ジャッジ日時 2024-10-10 20:49:14
合計ジャッジ時間 12,230 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 231 ms
31,728 KB
testcase_01 AC 52 ms
28,544 KB
testcase_02 AC 286 ms
66,436 KB
testcase_03 AC 230 ms
33,408 KB
testcase_04 AC 227 ms
33,280 KB
testcase_05 AC 52 ms
28,672 KB
testcase_06 AC 52 ms
30,548 KB
testcase_07 AC 51 ms
28,416 KB
testcase_08 AC 53 ms
28,672 KB
testcase_09 AC 297 ms
64,528 KB
testcase_10 AC 53 ms
28,672 KB
testcase_11 AC 161 ms
33,152 KB
testcase_12 AC 252 ms
38,424 KB
testcase_13 AC 249 ms
38,476 KB
testcase_14 AC 249 ms
38,472 KB
testcase_15 AC 255 ms
35,696 KB
testcase_16 AC 244 ms
35,456 KB
testcase_17 AC 240 ms
33,528 KB
testcase_18 AC 227 ms
188,284 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (96 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

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("ABCDABCD");
            WillReturn.Add("3");
            WillReturn.Add("A");
            WillReturn.Add("DA");
            WillReturn.Add("ABCDABCD");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("YUKICODER");
            WillReturn.Add("2");
            WillReturn.Add("X");
            WillReturn.Add("ABCDEFGHIJ");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("AAAA");
            WillReturn.Add("4");
            WillReturn.Add("A");
            WillReturn.Add("AA");
            WillReturn.Add("AAA");
            WillReturn.Add("AAAA");
            //10
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("ABAACABCAACBABABACBBAC");
            WillReturn.Add("7");
            WillReturn.Add("A");
            WillReturn.Add("C");
            WillReturn.Add("AA");
            WillReturn.Add("ABB");
            WillReturn.Add("ABA");
            WillReturn.Add("BA");
            WillReturn.Add("CBBAC");
            //26
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var InsRollingHash = new RollingHash(S);

        int UB = S.Length - 1;

        // 件数[ハッシュ値]なDict
        var CntDict = new Dictionary<decimal, long>();

        for (int LoopRange = 1; LoopRange <= 10; LoopRange++) {
            for (int RangeSta = 0; RangeSta <= UB; RangeSta++) {
                int RangeEnd = RangeSta + LoopRange - 1;
                if (RangeEnd > UB) break;
                decimal Hash = InsRollingHash.GetRangeHash(RangeSta, RangeEnd);
                if (CntDict.ContainsKey(Hash) == false) {
                    CntDict[Hash] = 0;
                }
                CntDict[Hash]++;
            }
        }

        long Answer = 0;
        foreach (string EachStr in InputList.Skip(2)) {
            var CurrRollingHash = new RollingHash(EachStr);
            int RangeSta = 0;
            int RangeEnd = EachStr.Length - 1;
            decimal CurrHash = CurrRollingHash.GetRangeHash(RangeSta, RangeEnd);

            if (CntDict.ContainsKey(CurrHash)) {
                Answer += CntDict[CurrHash];
            }
        }
        Console.WriteLine(Answer);
    }
}

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

    // ハッシュ値[終了Ind]で、[0,終了Ind]のハッシュ値を保持
    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
0