using System;
using System.Collections.Generic;
namespace ConsoleApp5
{
class Program
{
static void Main(string[] args)
{
var s = new RollingHash(Console.ReadLine());
var m = int.Parse(Console.ReadLine());
long count = 0;
for (int i = 0; i < m; i++)
{
var c = new RollingHash(Console.ReadLine());
var cHash = c[..];
for (int begin = 0; begin <= s.Length - c.Length; begin++)
{
if (cHash == s.Slice(begin, c.Length))
{
count++;
}
}
}
Console.WriteLine(count);
}
///
/// 参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
/// ジェネリクスに対応させるにはGetHashCode()を足していく?実装によっては重そうなのでとりあえずパス。
///
class RollingHash
{
const ulong Mask30 = (1UL << 30) - 1;
const ulong Mask31 = (1UL << 31) - 1;
const ulong Mod = (1UL << 61) - 1;
const ulong Positivizer = Mod * ((1UL << 3) - 1); // 引き算する前に足すことでmodが負になることを防ぐやつ
static readonly uint base1;
static readonly uint base2;
static readonly List pow1;
static readonly List pow2;
static RollingHash()
{
var random = new Random();
base1 = (uint)random.Next(129, int.MaxValue >> 2);
base2 = (uint)random.Next(int.MaxValue >> 2, int.MaxValue); // 32bit目は0にしておく
pow1 = new List() { 1 };
pow2 = new List() { 1 };
}
ulong[] hash1;
ulong[] hash2;
public int Length => hash1.Length - 1;
public RollingHash(ReadOnlySpan s)
{
hash1 = new ulong[s.Length + 1];
hash2 = new ulong[s.Length + 1];
for (int i = pow1.Count; i < s.Length + 1; i++)
{
pow1.Add(CalculateModular(Multiply(pow1[i - 1], base1)));
pow2.Add(CalculateModular(Multiply(pow2[i - 1], base2)));
}
for (int i = 0; i < s.Length; i++)
{
hash1[i + 1] = CalculateModular(Multiply(hash1[i], base1) + s[i]);
hash2[i + 1] = CalculateModular(Multiply(hash2[i], base2) + s[i]);
}
}
public (ulong, ulong) this[Range range]
{
get
{
var (offset, length) = range.GetOffsetAndLength(Length);
return Slice(offset, length);
}
}
public (ulong, ulong) Slice(int begin, int length)
{
var result1 = CalculateModular(hash1[begin + length] + Positivizer - Multiply(hash1[begin], pow1[length]));
var result2 = CalculateModular(hash2[begin + length] + Positivizer - Multiply(hash2[begin], pow2[length]));
return (result1, result2);
}
private static ulong Multiply(ulong l, ulong r)
{
var lu = l >> 31;
var ll = l & Mask31;
var ru = r >> 31;
var rl = r & Mask31;
var mid = ll * ru + lu * rl;
return ((lu * ru) << 1) + ll * rl + ((mid & Mask30) << 31) + (mid >> 30); // a * 2^61 ≡ a (mod 2^61 - 1)を使う
}
private static ulong Multiply(ulong l, uint r)
{
var lu = l >> 31;
var mid = lu * r;
return (l & Mask31) * r + ((mid & Mask30) << 31) + (mid >> 30); // rの32bit目は0としている
}
private static ulong CalculateModular(ulong value)
{
value = (value & Mod) + (value >> 61);
if (value >= Mod)
{
value -= Mod;
}
return value;
}
}
}
}