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 * Wrong solution: Strikethrough List *

* This is an O(n.sqrt(n)) solution that assumes no collisions. * It fails on one of the test cases. * * @author Martin Kacer */ public class StrikethroughListHashOnly { 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 StrikethroughListHashOnly().run(); } static final int MOD = 10000103, MUL = 37; 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<>(); 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; if (len > text.length) continue; for (int i = 0; i < len; ++i) mul2len = mul2len * MUL % MOD; byHash.clear(); for (String w : me.getValue()) { int hash = 0; for (char c : w.toCharArray()) hash = (hash * MUL + c) % MOD; byHash.add(hash); } int hash = 0; for (int i = 0; i < len; ++i) hash = (hash * MUL + text[i]) % MOD; for (int i = len; ; ++i) { if (maxlen[i-len] < len && byHash.contains(hash)) 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; } } 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; } }