結果
問題 | No.430 文字列検索 |
ユーザー | ひばち |
提出日時 | 2019-08-16 15:18:06 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 6,977 bytes |
コンパイル時間 | 2,439 ms |
コンパイル使用メモリ | 118,632 KB |
実行使用メモリ | 48,264 KB |
最終ジャッジ日時 | 2024-11-10 00:29:03 |
合計ジャッジ時間 | 3,894 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
19,328 KB |
testcase_01 | AC | 225 ms
48,264 KB |
testcase_02 | AC | 137 ms
20,608 KB |
testcase_03 | AC | 138 ms
20,992 KB |
testcase_04 | AC | 35 ms
19,200 KB |
testcase_05 | AC | 34 ms
19,072 KB |
testcase_06 | AC | 34 ms
19,072 KB |
testcase_07 | AC | 34 ms
19,328 KB |
testcase_08 | AC | 219 ms
48,048 KB |
testcase_09 | AC | 37 ms
19,328 KB |
testcase_10 | AC | 50 ms
23,168 KB |
testcase_11 | AC | 153 ms
26,112 KB |
testcase_12 | AC | 153 ms
26,112 KB |
testcase_13 | AC | 153 ms
26,240 KB |
testcase_14 | AC | 152 ms
23,552 KB |
testcase_15 | AC | 151 ms
23,552 KB |
testcase_16 | AC | 139 ms
20,864 KB |
testcase_17 | AC | 138 ms
20,608 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; using System.IO; using static System.Console; using static System.Convert; using static System.Math; //using static System.Globalization.CultureInfo; using System.Text; class Program { private static void chmin<T>(ref T num, T val) where T : IComparable<T> => num = num.CompareTo(val) == 1 ? val : num; private static void chmax<T>(ref T num, T val) where T : IComparable<T> => num = num.CompareTo(val) == -1 ? val : num; static void Main(string[] args) { var pr = new Program(); var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw); pr.Solve(); Console.Out.Flush(); } void Solve() { var str = ReadLine(); var num = Input.num; var mod = (int)1e9 + 7; var bs = new[] { 1009, 1007 }; var hash = Enumerable.Repeat(0, bs.Length).Select(_ => new long[str.Length + 1]).ToArray(); var pow = Enumerable.Repeat(0, bs.Length).Select(_ => new long[str.Length + 1]).ToArray(); pow[0][0] = pow[1][0] = 1; for(var p=0;p<bs.Length;p++) for(var i=1;i<=str.Length;i++) { hash[p][i] = (hash[p][i - 1] + str[i - 1])*bs[p] % mod; pow[p][i] = pow[p][i - 1] * bs[p] % mod; } var dic = Enumerable.Repeat(0, bs.Length).Select(_ => new Dictionary<int, int>()).ToArray(); for(var p=0;p<bs.Length;p++) for (var k = 0; k < 10; k++) for (var i = 0; i < str.Length - k; i++) { var cl = (int)(((hash[p][i + k + 1] - hash[p][i] * pow[p][k + 1]) % mod + mod) % mod); if (dic[p].ContainsKey(cl)) dic[p][cl]++; else dic[p][cl] = 1; } var res = Enumerable.Repeat(0L, bs.Length).ToArray(); while (num-- > 0) { var t = ReadLine(); var h = new long[bs.Length]; for (var p = 0; p < bs.Length; p++) for (var i = 0; i < t.Length; i++) h[p] = (h[p] + t[i]) * bs[p] % mod; for (var i = 0; i < bs.Length; i++) if (dic[i].ContainsKey((int)h[i])) res[i] += dic[i][(int)h[i]]; } WriteLine(res.Min()); } } public class Input { public static string read => ReadLine().Trim(); public static int[] ar => read.Split(' ').Select(int.Parse).ToArray(); public static int num => ToInt32(read); public static long[] arL => read.Split(' ').Select(long.Parse).ToArray(); public static long numL => ToInt64(read); public static T[] create<T>(int n, Func<int, T> f) => Enumerable.Repeat(0, n).Select(f).ToArray(); public static char[][] gred(int h) => create(h, _ => read.ToCharArray()); public static int[] ar1D(int n) => create(n, _ => num); public static long[] arL1D(int n) => create(n, _ => numL); public static string[] strs(int n) => create(n, _ => read); public static int[][] ar2D(int n) => create(n, _ => ar); public static long[][] arL2D(int n) => create(n, _ => arL); public static List<T>[] edge<T>(int n) => create(n, _ => new List<T>()); public static T GetValue<T>(string g) { var t = typeof(T); if (t == typeof(int)) return (T)(object)int.Parse(g); if (t == typeof(long)) return (T)(object)long.Parse(g); if (t == typeof(string)) return (T)(object)g; if (t == typeof(char)) return (T)(object)char.Parse(g); if (t == typeof(double)) return (T)(object)double.Parse(g); if (t == typeof(bool)) return (T)(object)bool.Parse(g); return default(T); } public static void Make<T1, T2>(out T1 v1, out T2 v2) { v1 = Next<T1>(); v2 = Next<T2>(); } public static void Make<T1, T2, T3>(out T1 v1, out T2 v2, out T3 v3) { Make(out v1, out v2); v3 = Next<T3>(); } public static void Make<T1, T2, T3, T4>(out T1 v1, out T2 v2, out T3 v3, out T4 v4) { Make(out v1, out v2, out v3); v4 = Next<T4>(); } public static void Make<T1, T2, T3, T4, T5>(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5) { Make(out v1, out v2, out v3, out v4); v5 = Next<T5>(); } public static void Make<T1, T2, T3, T4, T5, T6>(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6) { Make(out v1, out v2, out v3, out v4, out v5); v6 = Next<T6>(); } private static Queue<string> sc; public static T Next<T>(){ sc = sc ?? new Queue<string>(); if (sc.Count == 0) foreach (var item in read.Split(' ')) sc.Enqueue(item);return GetValue<T>(sc.Dequeue()); } public static void Next<T>(ref T val) => val = Next<T>(); public const long Inf = (long)1e18; public const double eps = 1e-6; public const string Alfa = "abcdefghijklmnopqrstuvwxyz"; public const int MOD = 1000000007; } public class Pair<T1, T2> : IComparable<Pair<T1, T2>> { public T1 v1 { get; set; } public T2 v2 { get; set; } public Pair() { v1 = Input.Next<T1>(); v2 = Input.Next<T2>(); } public Pair(T1 v1, T2 v2) { this.v1 = v1; this.v2 = v2; } public int CompareTo(Pair<T1, T2> p) { var c = Comparer<T1>.Default.Compare(v1, p.v1); if (c == 0) c = Comparer<T2>.Default.Compare(v2, p.v2); return c; } public override string ToString() => $"{v1.ToString()} {v2.ToString()}"; public override bool Equals(object obj) => this == (Pair<T1, T2>)obj; public override int GetHashCode() => v1.GetHashCode() ^ v2.GetHashCode(); public static bool operator ==(Pair<T1, T2> p1, Pair<T1, T2> p2) => p1.CompareTo(p2) == 0; public static bool operator !=(Pair<T1, T2> p1, Pair<T1, T2> p2) => p1.CompareTo(p2) != 0; public static bool operator >(Pair<T1, T2> p1, Pair<T1, T2> p2) => p1.CompareTo(p2) == 1; public static bool operator >=(Pair<T1, T2> p1, Pair<T1, T2> p2) => p1.CompareTo(p2) != -1; public static bool operator <(Pair<T1, T2> p1, Pair<T1, T2> p2) => p1.CompareTo(p2) == -1; public static bool operator <=(Pair<T1, T2> p1, Pair<T1, T2> p2) => p1.CompareTo(p2) != 1; } public class Pair<T1, T2, T3> : Pair<T1, T2>, IComparable<Pair<T1, T2, T3>> { public T3 v3 { get; set; } public Pair() : base() { v3 = Input.Next<T3>(); } public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2) { this.v3 = v3; } public int CompareTo(Pair<T1, T2, T3> p) { var c = base.CompareTo(p); if (c == 0) c = Comparer<T3>.Default.Compare(v3, p.v3); return c; } public override string ToString() => $"{base.ToString()} {v3.ToString()}"; }