#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]; } } } /// /// Mods[i]におけるS[l,r)のハッシュを取得 /// 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]}"; } /// /// 全てのModsにおけるs[l,r)のハッシュを取得 /// public long[] GetHashes(int l, int r) { List hashList = new List(); for (int i = 0; i < Mods.Length; i++) { hashList.Add(GetHash(l, r, i)); } return hashList.ToArray(); } /// /// 全てのModsでS[l,r)が一致するか /// 2つのhashを比較する /// 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; } /// /// 最長共通接頭辞の長さ /// this.S[l1:]とother.S[l2:] /// 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; } /// /// 最長共通接頭辞の長さ /// public int GetLcp(int l1, int l2) { return GetLcp(this, l1, l2); } /// /// this.S[l1:]がotherで始まっているか /// 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 inputStream; public ConsoleInput(TextReader stream, char separator = ' ') { _separator = separator; _stream = stream; inputStream = new Queue(); } 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 }