結果
| 問題 |
No.430 文字列検索
|
| コンテスト | |
| ユーザー |
 utaka
|
| 提出日時 | 2019-09-16 19:33:33 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,568 bytes |
| コンパイル時間 | 2,249 ms |
| コンパイル使用メモリ | 111,872 KB |
| 実行使用メモリ | 29,312 KB |
| 最終ジャッジ日時 | 2024-11-10 00:32:17 |
| 合計ジャッジ時間 | 5,660 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | AC * 1 TLE * 1 -- * 12 |
コンパイルメッセージ
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;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Linq;
using System.Net.Mime;
using System.Net.NetworkInformation;
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);
string S = cin.Read;
int M = cin.ReadInt;
var rh = new RollingHash<char>(S.ToCharArray());
long ans = 0;
for (int q = 0; q < M; q++)
{
string c = cin.Read;
int count = 0;
var rh2 = new RollingHash<char>(c.ToCharArray());
for (int i = 0; i < S.Length - c.Length + 1; i++)
{
if (rh.isSame(i, 0, c.Length + i, c.Length, rh2))
{
count++;
}
}
ans += count;
}
console.WriteLine(ans.ToString());
}
}
class RollingHash<T> where T : IComparable<T>, IConvertible
{
int[] mod = {(int)(1e9 + 7), (int)(1e9 + 9), 1234567891};
int[] K = {1007, 1009, 1013};
public T[] S;
long[,] hash;
long[,] powTable;
public RollingHash(T[] S)
{
this.S = S;
hash = new long[mod.Length, S.Length + 1];
for (int i = 0; i < mod.Length; i++)
{
for (int j = S.Length - 1; j >= 0; j--)
{
hash[i, j] = hash[i, j + 1] * K[i];
hash[i, j] += Convert.ToInt64(S[j]);
hash[i, j] %= mod[i];
}
}
powTable = new long[mod.Length, S.Length + 1];
for (int i = 0; i < mod.Length; i++)
{
powTable[i, 0] = 1;
for (int j = 1; j < S.Length + 1; j++)
{
powTable[i, j] = (powTable[i, j - 1] * K[i]) % mod[i];
}
}
}
public long getHash(int t, int start, int end)
{
long r = hash[t, start] - hash[t, end] * powTable[t, end - start];
r %= mod[t];
if (r < 0) r += mod[t];
return r;
}
public bool isSame(int Astart, int Bstart, int Aend, int Bend)
{
int len = Aend - Astart;
if (len != Bend - Bstart) return false;
for (int i = 0; i < mod.Length; i++)
{
if (getHash(i, Astart, Aend) != getHash(i, Bstart, Bend)) return false;
}
return true;
}
public bool isSame(int Astart, int Bstart, int Aend, int Bend, RollingHash<T> rh)
{
if (rh == null) return isSame(Astart, Bstart, Aend, Bend);
int len = Aend - Astart;
if (len != Bend - Bstart) return false;
for (int i = 0; i < mod.Length; i++)
{
if (getHash(i, Astart, Aend) != rh.getHash(i, Bstart, Bend)) return false;
}
return true;
}
public int compare(int Astart, int Bstart, int Aend, int Bend, RollingHash<T> rh = null)
{
int Alen = Aend - Astart;
int Blen = Bend - Bstart;
int len = Math.Min(Alen, Blen);
int maxlen = len + 1;
int minlen = 0;
while (minlen + 1 < maxlen)
{
int nextlen = (maxlen + minlen) / 2;
if (isSame(Astart, Bstart, Astart + nextlen, Bstart + nextlen, rh))
{
minlen = nextlen;
}
else
{
maxlen = nextlen;
}
}
if (Astart + minlen == Aend)
{
if (Bstart + minlen == Bend) return 0;
else return -1;
}
else
{
if (Bstart + minlen == Bend) return 1;
else return S[Astart + minlen].CompareTo(S[Bstart + minlen]);
}
}
public int compare(int Astart, int Bstart)
{
if (revSA != null)
{
return revSA[Astart].CompareTo(revSA[Bstart]);
}
return compare(Astart, Bstart, S.Length, S.Length);
}
public int compare(int Astart, int Bstart, RollingHash<T> rh)
{
return compare(Astart, Bstart, S.Length, rh.S.Length);
}
public int[] SA;
public int[] revSA;
public int[] makeSuffixArray()
{
SA = new int[S.Length];
for (int i = 0; i < S.Length; i++)
{
SA[i] = i;
}
Array.Sort(SA, compare);
revSA = new int[S.Length];
for (int i = 0; i < S.Length; i++)
{
revSA[SA[i]] = i;
}
return SA;
}
}
public partial class Program
{
public const int ModLarge = 1000000007;
}
public class ConsoleInput
{
private readonly TextReader _stream;
private readonly char _separator = ' ';
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
}