import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; import java.util.StringTokenizer; /** * ICPC Central Europe Contest 2018 * Sample solution: ABCD Murderer *

* This should be a O(n.sqrt(n)) solution with much lower constants. * It uses double hashing and assumes no collisions. * * @author Martin Kacer */ public class StrikethroughListDoubleHash { StringTokenizer st = new StringTokenizer(""); BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); String nextLine() { try { return input.readLine(); } catch (IOException ex) { throw new RuntimeException(ex); } } public static void main(String[] args) { new StrikethroughListDoubleHash().run(); } static final int MOD = 10000103, MUL = 37, MOD2 = 7368787, MUL2 = 101; static class Word { final String word; int lastMatch = -1, period; Word(String w) { word = w; } } char[] text; Map> byLength = new HashMap<>(); Set byHash = new HashSet<>(), byHash2 = new HashSet<>(); int[] maxlen; boolean checkPeriod(String w, int per) { if (w.length() % per != 0) return false; for (int i = per; i < w.length(); i += per) for (int j = 0; j < per; ++j) if (w.charAt(j) != w.charAt(i+j)) return false; return true; } void run() { int words = Integer.valueOf(nextLine()); text = nextLine().toCharArray(); for (int i = 0; i < words; ++i) { String w = nextLine(); List blen = byLength.get(w.length()); if (blen == null) byLength.put(w.length(), blen = new ArrayList<>()); blen.add(w); } maxlen = new int[text.length]; for (Map.Entry> me : byLength.entrySet()) { int len = me.getKey(), mul2len = 1, mul2len2 = 1; if (len > text.length) continue; for (int i = 0; i < len; ++i) { mul2len = mul2len * MUL % MOD; mul2len2 = mul2len2 * MUL2 % MOD2; } byHash.clear(); byHash2.clear(); for (String w : me.getValue()) { int hash = 0, hash2 = 0; for (char c : w.toCharArray()) { hash = (hash * MUL + c) % MOD; hash2 = (hash2 * MUL2 + c) % MOD2; } byHash.add(hash); byHash2.add(hash2); } int hash = 0, hash2 = 0; for (int i = 0; i < len; ++i) { hash = (hash * MUL + text[i]) % MOD; hash2 = (hash2 * MUL2 + text[i]) % MOD2; } for (int i = len; ; ++i) { if (maxlen[i-len] < len && byHash.contains(hash) && byHash2.contains(hash2)) maxlen[i-len] = len; if (i == text.length) break; hash = (hash * MUL) + text[i] - mul2len * text[i-len]; if (hash < 0) hash += MOD * (-hash / MOD + 1); hash %= MOD; hash2 = (hash2 * MUL2) + text[i] - mul2len2 * text[i-len]; if (hash2 < 0) hash2 += MOD2 * (-hash2 / MOD2 + 1); hash2 %= MOD2; } } System.out.println(countResult()); } int countResult() { int cnt = 0, next = 0, reach = 0; for (int i = 0; i < text.length; ++i) { if (i + maxlen[i] > reach) reach = i + maxlen[i]; if (i == next) { if (reach <= i) return -1; ++cnt; next = reach; } } return cnt; } }