結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 utaka
|
| 提出日時 | 2019-09-16 23:36:25 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,065 bytes |
| コンパイル時間 | 3,520 ms |
| コンパイル使用メモリ | 108,448 KB |
| 実行使用メモリ | 28,060 KB |
| 最終ジャッジ日時 | 2023-09-21 08:11:40 |
| 合計ジャッジ時間 | 7,178 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 60 ms
22,980 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.
ソースコード
#if true
//#if false
#define UTAKA_DEBUG
#endif
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace UtakaApp
{
public partial class Program
{
public const string ContestName = "430";
public const string ProblemName = "";
public static void Main(string[] args)
{
#if UTAKA_LOCAL
//#if false
new TestCaseChecker().TestProblems();
#else
var console = new MyConsole();
new Program().Solve(System.Console.In, console);
console.Flush();
#endif
var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
}
public void Solve(TextReader textReader, IConsole console)
{
var cin = new ConsoleInput(textReader);
var S = cin.Read;
var M = cin.ReadInt;
var rh = new StringRollingHash(S);
long ans = 0;
for (var q = 0; q < M; q++)
{
var c = cin.Read;
var rh2 = new StringRollingHash(c);
var count = 0;
for (var i = 0; i < S.Length - c.Length + 1; i++)
{
if (rh.Match(rh2, i, 0, c.Length))
{
count++;
}
}
ans += count;
// int count = rh.compare(0, 0, rh2);
//
// if (count >= 0)
// {
// ans += count;
// }
}
console.WriteLine(ans.ToString());
}
}
public class StringRollingHash
{
private static readonly long[] Mods = {999999893, 999999937};
private static readonly long Base = 1013;
private readonly long[,] Hashes;
private readonly long[,] Powers;
private readonly string S;
public StringRollingHash(string s)
{
int modCount = Mods.Length;
S = s;
Hashes = new long[modCount, s.Length + 1];
Powers = new long[modCount, s.Length + 1];
for (int i = 0; i < modCount; i++)
{
Powers[i, 0] = 1;
for (int j = 0; j < s.Length; j++)
{
Hashes[i, j + 1] = (Hashes[i, j] * Base + s[j]) % Mods[i];
Powers[i, j + 1] = Powers[i, j] * Base % Mods[i];
}
}
}
/// <summary>
/// Mods[i]におけるS[l,r)のハッシュを取得
/// </summary>
private long GetHash(int l, int r, int i)
{
long res = (Hashes[i, r] - Hashes[i, l] * Powers[i, r - l]) % Mods[i];
if (res < 0)
{
res += Mods[i];
}
return res;
}
public string GetAllHashString(int l, int r)
{
long[] a = GetHashes(l, r);
return $"{a[0]}{a[1]}";
}
/// <summary>
/// 全てのModsにおけるs[l,r)のハッシュを取得
/// </summary>
public long[] GetHashes(int l, int r)
{
List<long> hashList = new List<long>();
for (int i = 0; i < Mods.Length; i++)
{
hashList.Add(GetHash(l, r, i));
}
return hashList.ToArray();
}
/// <summary>
/// 全てのModsでS[l,r)が一致するか
/// 2つのhashを比較する
/// </summary>
public bool Match(StringRollingHash other, int l1, int l2, int len)
{
// 範囲外
if (S.Length < l1 + len || other.S.Length < l2 + len)
{
return false;
}
for (var i = 0; i < Mods.Length; i++)
{
if (GetHash(l1, l1 + len, i) != other.GetHash(l2, l2 + len, i))
{
return false;
}
}
return true;
}
/// <summary>
/// 最長共通接頭辞の長さ
/// this.S[l1:]とother.S[l2:]
/// </summary>
public int GetLcp(StringRollingHash other, int l1, int l2)
{
var len = Math.Min(S.Length - l1, other.S.Length - l2);
int low = -1, high = len + 1;
while (high - low > 1)
{
var mid = low + (high - low) / 2;
if (!Match(other, l1, l2, mid))
{
high = mid;
}
else
{
low = mid;
}
}
return low;
}
/// <summary>
/// 最長共通接頭辞の長さ
/// </summary>
public int GetLcp(int l1, int l2)
{
return GetLcp(this, l1, l2);
}
/// <summary>
/// this.S[l1:]がotherで始まっているか
/// </summary>
public bool BeginWith(StringRollingHash other, int l1)
{
return Match(other, l1, 0, other.S.Length);
}
}
public partial class Program
{
public const int ModLarge = 1000000007;
}
public class ConsoleInput
{
private readonly char _separator = ' ';
private readonly TextReader _stream;
private readonly Queue<string> inputStream;
public ConsoleInput(TextReader stream, char separator = ' ')
{
_separator = separator;
_stream = stream;
inputStream = new Queue<string>();
}
public string Read
{
get
{
if (inputStream.Count != 0)
{
return inputStream.Dequeue();
}
var tmp = _stream.ReadLine().Split(_separator);
for (var i = 0; i < tmp.Length; ++i)
{
inputStream.Enqueue(tmp[i]);
}
return inputStream.Dequeue();
}
}
public string ReadLine => _stream.ReadLine();
public int ReadInt => int.Parse(Read);
public long ReadLong => long.Parse(Read);
public double ReadDouble => double.Parse(Read);
public string[] ReadStrArray(long N)
{
var ret = new string[N];
for (long i = 0; i < N; ++i)
{
ret[i] = Read;
}
return ret;
}
public int[] ReadIntArray(long N)
{
var ret = new int[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadInt;
}
return ret;
}
public long[] ReadLongArray(long N)
{
var ret = new long[N];
for (long i = 0; i < N; ++i)
{
ret[i] = ReadLong;
}
return ret;
}
}
public interface IConsole
{
void Flush();
void Write(string str);
void WriteLine(string str);
}
public class MyConsole : IConsole
{
public MyConsole()
{
var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
Console.SetOut(sw);
}
public void Flush()
{
Console.Out.Flush();
}
public void Write(string str)
{
Console.Write(str);
}
public void WriteLine(string str)
{
Console.WriteLine(str);
}
}
#if UTAKA_LOCAL
public class DebugConsole : IConsole
{
private readonly StringBuilder mSb;
public DebugConsole()
{
mSb = new StringBuilder();
}
public void Flush()
{
// 何もしない
}
public void Write(string str)
{
mSb.Append(str);
}
public void WriteLine(string str)
{
mSb.AppendLine(str);
}
public string GetAllOutput()
{
return mSb.ToString();
}
}
#endif
#if UTAKA_LOCAL
public class TestCaseChecker
{
// private string DirectoryPath => $"../../../../{Program.ContestName}/{Program.ProblemName}";
private string DirectoryPath => $"../../../../{Program.ContestName}";
private string GetInputFilePath(int testCaseNumber)
{
return $"{DirectoryPath}/sample-{testCaseNumber}.in";
// return $"{DirectoryPath}/in_{testCaseNumber}.txt";
}
private string GetOutputFilePath(int testCaseNumber)
{
return $"{DirectoryPath}/sample-{testCaseNumber}.out";
// return $"{DirectoryPath}/out_{testCaseNumber}.txt";
}
public bool TestProblem(int testCaseNumber)
{
var inputFilePath = GetInputFilePath(testCaseNumber);
var outputFilePath = GetOutputFilePath(testCaseNumber);
TextReader inputStream = new StreamReader(inputFilePath);
var debugConsoleWriter = new DebugConsole();
new Program().Solve(inputStream, debugConsoleWriter);
var output = debugConsoleWriter.GetAllOutput();
TextReader outputStream = new StreamReader(outputFilePath);
var outputAnswer = outputStream.ReadToEnd();
Dbg.WriteLine(output);
Dbg.WriteLine(outputAnswer);
var isCorrect = output == outputAnswer;
return isCorrect;
}
public void TestProblems()
{
var isSuccessAll = true;
var testCaseNumber = 1;
while (true)
{
var inputFileName = GetInputFilePath(testCaseNumber);
if (!File.Exists(inputFileName))
{
break;
}
Console.WriteLine($"TestCase {testCaseNumber} =====================================================");
var result = TestProblem(testCaseNumber);
if (result)
{
Console.WriteLine("Success");
}
else
{
isSuccessAll = false;
Console.WriteLine("Failure *****");
}
testCaseNumber++;
}
if (isSuccessAll)
{
Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!");
}
}
}
#endif
#if UTAKA_LOCAL
public static class Dbg
{
public static void WriteLine(string str)
{
Console.WriteLine(str);
}
public static void Write(string str)
{
Console.Write(str);
}
}
#else
public static class Dbg
{
public static void WriteLine(string str)
{
}
public static void Write(string str)
{
}
}
#endif
}