#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(S.ToCharArray()); long ans = 0; for (int q = 0; q < M; q++) { string c = cin.Read; int count = 0; var rh2 = new RollingHash(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 where T : IComparable, 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 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 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 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 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 }