using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/430 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); 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 InputList = GetInputList(); string S = InputList[0]; var InsRollingHash = new RollingHash(S); int UB = S.Length - 1; // 件数[ハッシュ値]なDict var CntDict = new Dictionary(); for (int LoopRange = 1; LoopRange <= 10; LoopRange++) { for (int RangeSta = 0; RangeSta <= UB; RangeSta++) { int RangeEnd = RangeSta + LoopRange - 1; if (RangeEnd > UB) break; long 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; long CurrHash = CurrRollingHash.GetRangeHash(RangeSta, RangeEnd); if (CntDict.ContainsKey(CurrHash)) { Answer += CntDict[CurrHash]; } } Console.WriteLine(Answer); } } #region RollingHash // ローリングハッシュ internal class RollingHash { const long Base = 100; const long Hou = 1000000007; // ハッシュ値[終了Ind]で、[0,終了Ind]のハッシュ値を保持 long[] mHashArr; // 桁の重みの配列 long[] mOmomiArr; // コンストラクタ internal RollingHash(string pTargetStr) { long Omomi = 1; long UB = pTargetStr.Length - 1; mHashArr = new long[UB + 1]; mOmomiArr = new long[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 long GetRangeHash(long pSta, long pEnd) { long WillReturn = mHashArr[pEnd]; if (pSta > 0) { long Range = pEnd - pSta + 1; long PrevVal = mHashArr[pSta - 1]; long MinusVal = PrevVal * mOmomiArr[Range]; MinusVal %= Hou; WillReturn -= MinusVal; if (WillReturn < 0) { WillReturn += Hou; } } return WillReturn; } } #endregion