結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 mnzn
|
| 提出日時 | 2020-04-13 11:40:53 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,565 bytes |
| コンパイル時間 | 3,195 ms |
| コンパイル使用メモリ | 111,320 KB |
| 実行使用メモリ | 28,332 KB |
| 最終ジャッジ日時 | 2023-10-24 21:07:26 |
| 合計ジャッジ時間 | 5,680 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 23 ms
28,332 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
コンパイルメッセージ
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;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Program
{
static void Main(string[] args)
{
var S = sc.ReadStr();
var M = sc.ReadInt();
var rhs = new RollingHash(S);
var ans = 0;
for (int i = 0; i < M; i++)
{
var T = sc.ReadStr();
if (T.Length > S.Length) continue;
var rht = new RollingHash(T);
var hashT = rht.Get(0, T.Length);
for (int j = 0; j < S.Length - T.Length + 1; j++)
{
var hashS = rhs.Get(j, j + T.Length);
if (hashT == hashS) ans++;
}
}
Console.WriteLine(ans);
}
class RollingHash
{
public const long B = (long)1e5 + 7;
public const long MOD = (long)1e9 + 7;
public string S { get; set; }
public int N { get; set; }
public long[] Power { get; set; }
public long[] Hash { get; set; }
public RollingHash(string s)
{
this.S = s;
this.N = s.Length;
// B^nを計算しておく
this.Power = new long[this.N + 1];
this.Power[0] = 1;
for (int i = 0; i < N; i++)
{
this.Power[i + 1] = (this.Power[i] * B) % MOD;
}
// ハッシュを前計算する
this.Hash = new long[this.N + 1];
for (int i = 0; i < N; i++)
{
this.Hash[i + 1] = (this.Hash[i] * B + S[i]) % MOD;
}
}
// [l, r) のハッシュ値を求める
public long Get(int l, int r)
{
var hash = this.Hash[r] - (this.Hash[l] * this.Power[r - l] % MOD);
if (hash < 0) hash += MOD;
return hash;
}
// S[a:] and S[b:]
public int GetLCP(int a, int b)
{
var len = Math.Min(N - a, N - b) + 1;
var l = 0;
var r = len;
while (r - l > 1)
{
var mid = l + (r - l) / 2;
var hashA = this.Get(a, a + mid);
var hashB = this.Get(b, b + mid);
if (hashA == hashB) l = mid;
else r = mid;
}
return l;
}
// S[a:] and T[b:]
public int GetLCP(RollingHash rollingHash, int a, int b)
{
var len = Math.Min(rollingHash.S.Length - a, N - b) + 1;
var l = 0;
var r = len;
while (r - l > 1)
{
var mid = l + (r - l) / 2;
var hash1 = this.Get(b, b + mid);
var hash2 = rollingHash.Get(a, a + mid);
if (hash1 == hash2) l = mid;
else r = mid;
}
return l;
}
}
static Scanner sc = new Scanner();
}
class Scanner
{
string[] S = new string[0];
int Index = 0;
char[] Separators = new char[] { ' ' };
public string Next()
{
if (this.Index < this.S.Length) return this.S[this.Index++];
var line = "";
while (line == "") line = Console.ReadLine();
this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
if (this.S.Length == 0) return this.Next();
this.Index = 0;
return this.S[this.Index++];
}
public string ReadStr()
{
return this.Next();
}
public char ReadChar()
{
return this.Next()[0];
}
public int ReadInt()
{
return int.Parse(this.Next());
}
public uint ReadUInt()
{
return uint.Parse(this.Next());
}
public long ReadLong()
{
return long.Parse(this.Next());
}
public double ReadDouble()
{
return double.Parse(this.Next());
}
public Tuple<int, int> ReadTup(int add = 0)
{
return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add);
}
public Tuple<long, long> ReadTupLong(int add = 0)
{
return Tuple.Create(this.ReadLong() + add, this.ReadLong() + add);
}
public Tuple<int, int, int> ReadTup3(int add = 0)
{
return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add);
}
public Tuple<int, int, int, int> ReadTup4(int add = 0)
{
return Tuple.Create(this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add, this.ReadInt() + add);
}
public int[] ReadIntArray(int n)
{
var array = new int[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadInt();
}
return array;
}
public long[] ReadLongArray(int n)
{
var array = new long[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadLong();
}
return array;
}
public double[] ReadDoubleArray(int n)
{
var array = new double[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadDouble();
}
return array;
}
public char[] ReadCharArray(int n)
{
var array = new char[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadChar();
}
return array;
}
public string[] ReadStrArray(int n)
{
var array = new string[n];
for (int i = 0; i < array.Length; i++)
{
array[i] = this.ReadStr();
}
return array;
}
public Tuple<long, long>[] ReadTupLongArray(int n, int add = 0)
{
var array = new Tuple<long, long>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTupLong(add);
}
return array;
}
public Tuple<int, int>[] ReadTupArray(int n, int add = 0)
{
var array = new Tuple<int, int>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTup(add);
}
return array;
}
public Tuple<int, int, int>[] ReadTup3Array(int n, int add = 0)
{
var array = new Tuple<int, int, int>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTup3(add);
}
return array;
}
public Tuple<int, int, int, int>[] ReadTup4Array(int n, int add = 0)
{
var array = new Tuple<int, int, int, int>[n];
for (int i = 0; i < n; i++)
{
array[i] = this.ReadTup4(add);
}
return array;
}
}