Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class eticket_pk {
- BufferedReader br;
- PrintWriter out;
- StringTokenizer st;
- public String nextToken() throws IOException {
- while ((st == null) || (!st.hasMoreTokens()))
- st = new StringTokenizer(br.readLine());
- return st.nextToken();
- }
- public int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- public double nextDouble() throws IOException {
- return Double.parseDouble(nextToken());
- }
- public long nextLong() throws IOException {
- return Long.parseLong(nextToken());
- }
- final long C1 = 17239;
- long hash(String s) {
- long res = 0;
- for (int i = 0; i < s.length(); i++) {
- res = res * C1 + s.charAt(i);
- }
- return res;
- }
- boolean check(Set<Long> voc, int n, ArrayDeque<Long>[] h,
- ArrayDeque<Integer>[] l, long[] pow) {
- if (!voc.contains(h[0].getFirst()))
- return false;
- if (!voc.contains(h[n - 1].getLast()))
- return false;
- for (int i = 0; i < n - 1; i++) {
- if (!voc.contains(h[i].getLast() * pow[l[i + 1].getFirst()]
- + h[i + 1].getFirst())) {
- return false;
- }
- }
- return true;
- }
- public void solve() throws IOException {
- HashSet<Long> voc = new HashSet<Long>();
- voc.add((long) 0);
- int k = nextInt();
- assert((1 <= k) && (k <= 2000));
- for (int i = 0; i < k; i++) {
- String s = nextToken();
- long x = hash(s);
- assert (!voc.contains(x));
- for (int j = 0; j < s.length(); j++)
- assert(('a' <= s.charAt(j)) && (s.charAt(j) <= 'z'));
- assert((1 <= s.length()) && (s.length() <= 2000));
- voc.add(x);
- }
- int badCount = 0;
- int n = nextInt();
- assert((1 <= n) && (n <= 2000));
- String[] s = new String[n];
- for (int i = 0; i < n; i++) {
- s[i] = br.readLine();
- assert((s[i].length() >= 1) && (s[i].length() <= 2000));
- if (i > 0)
- assert(s[i].length() == s[i - 1].length());
- boolean fl = false;
- for (int j = 0; j < s[i].length(); j++) {
- assert((('a' <= s[i].charAt(j)) && (s[i].charAt(j) <= 'z')) || (s[i].charAt(j) == '.'));
- fl = fl || s[i].charAt(j) == '.';
- }
- assert(fl);
- }
- ArrayDeque<Integer>[] l = new ArrayDeque[n];
- ArrayDeque<Long>[] h = new ArrayDeque[n];
- for (int i = 0; i < n; i++) {
- long tH = 0;
- int tL = 0;
- h[i] = new ArrayDeque<Long>();
- l[i] = new ArrayDeque<Integer>();
- for (int j = 0; j < s[i].length(); j++) {
- if (s[i].charAt(j) == '.') {
- if ((tH != 0) || (h[i].size() == 0)) {
- h[i].add(tH);
- if (!voc.contains(tH))
- badCount++;
- l[i].add(tL);
- tL = 0;
- tH = 0;
- }
- } else {
- tH = tH * C1 + s[i].charAt(j);
- tL++;
- }
- }
- if ((l[i].size() == 0) || (l[i].getLast() != 0) || (tL > 0)) {
- l[i].add(tL);
- h[i].add(tH);
- if (!voc.contains(tH))
- badCount++;
- }
- }
- long[] pow = new long[s[0].length() + 10];
- pow[0] = 1;
- for (int i = 1; i < pow.length; i++) {
- pow[i] = pow[i - 1] * C1;
- }
- ArrayList<Integer> ans = new ArrayList<Integer>();
- for (int i = 0; i < n; i++) {
- if (!voc.contains(h[i].getFirst()))
- badCount--;
- if ((!voc.contains(h[i].getLast())) && (h[i].size() > 1))
- badCount--;
- }
- for (int i = 0; i < s[0].length(); i++) {
- if ((check(voc, n, h, l, pow)) && (badCount == 0))
- ans.add(i);
- for (int j = 0; j < n; j++) {
- if (s[j].charAt(i) != '.') {
- h[j].addLast(h[j].removeLast() * C1 + s[j].charAt(i));
- h[j].addFirst(h[j].removeFirst() - s[j].charAt(i)
- * pow[l[j].getFirst() - 1]);
- l[j].addLast(l[j].removeLast() + 1);
- l[j].addFirst(l[j].removeFirst() - 1);
- } else {
- if ((l[j].getFirst() == 0) && (s[j].charAt((i + 1 ) % s[j].length()) != '.')) {
- l[j].removeFirst();
- h[j].removeFirst();
- if ((h[j].size() > 0) && (!voc.contains(h[j].getFirst())))
- badCount--;
- }
- if ((l[j].size() == 0) || (l[j].getLast() != 0)) {
- if ((h[j].size() > 0) && (!voc.contains(h[j].getLast())))
- badCount++;
- l[j].addLast(0);
- h[j].addLast((long) 0);
- }
- }
- }
- }
- out.println(ans.size());
- for (int i = 0; i < ans.size(); i++) {
- out.print(ans.get(i));
- if (i < ans.size() - 1)
- out.print(' ');
- else
- out.println();
- }
- }
- public void run() {
- try {
- br = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- // br = new BufferedReader(new FileReader("eticket.in"));
- // out = new PrintWriter("eticket.out");
- solve();
- out.close();
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- public static void main(String[] args) {
- new eticket_pk().run();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement