daily pastebin goal
39%
SHARE
TWEET

Untitled

raliev May 29th, 2012 710 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class eticket_pk {
  5.  
  6.         BufferedReader br;
  7.         PrintWriter out;
  8.         StringTokenizer st;
  9.  
  10.         public String nextToken() throws IOException {
  11.                 while ((st == null) || (!st.hasMoreTokens()))
  12.                         st = new StringTokenizer(br.readLine());
  13.                 return st.nextToken();
  14.         }
  15.  
  16.         public int nextInt() throws IOException {
  17.                 return Integer.parseInt(nextToken());
  18.         }
  19.  
  20.         public double nextDouble() throws IOException {
  21.                 return Double.parseDouble(nextToken());
  22.         }
  23.  
  24.         public long nextLong() throws IOException {
  25.                 return Long.parseLong(nextToken());
  26.         }
  27.  
  28.         final long C1 = 17239;
  29.  
  30.         long hash(String s) {
  31.                 long res = 0;
  32.                 for (int i = 0; i < s.length(); i++) {
  33.                         res = res * C1 + s.charAt(i);
  34.                 }
  35.                 return res;
  36.         }
  37.  
  38.         boolean check(Set<Long> voc, int n, ArrayDeque<Long>[] h,
  39.                         ArrayDeque<Integer>[] l, long[] pow) {
  40.                 if (!voc.contains(h[0].getFirst()))
  41.                         return false;
  42.                 if (!voc.contains(h[n - 1].getLast()))
  43.                         return false;
  44.                 for (int i = 0; i < n - 1; i++) {
  45.                         if (!voc.contains(h[i].getLast() * pow[l[i + 1].getFirst()]
  46.                                         + h[i + 1].getFirst())) {
  47.                                 return false;
  48.                         }
  49.                 }
  50.                 return true;
  51.         }
  52.  
  53.         public void solve() throws IOException {
  54.                 HashSet<Long> voc = new HashSet<Long>();
  55.                 voc.add((long) 0);
  56.                 int k = nextInt();
  57.                 assert((1 <= k) && (k <= 2000));
  58.                 for (int i = 0; i < k; i++) {
  59.                         String s = nextToken();
  60.                         long x = hash(s);
  61.                         assert (!voc.contains(x));
  62.                         for (int j = 0; j < s.length(); j++)
  63.                                 assert(('a' <= s.charAt(j)) && (s.charAt(j) <= 'z'));
  64.                         assert((1 <= s.length()) && (s.length() <= 2000));
  65.                         voc.add(x);
  66.                 }
  67.                 int badCount = 0;
  68.                 int n = nextInt();
  69.                 assert((1 <= n) && (n <= 2000));
  70.                 String[] s = new String[n];
  71.                 for (int i = 0; i < n; i++) {
  72.                         s[i] = br.readLine();
  73.                         assert((s[i].length() >= 1) && (s[i].length() <= 2000));
  74.                         if (i > 0)
  75.                                 assert(s[i].length() == s[i - 1].length());
  76.                         boolean fl = false;
  77.                         for (int j = 0; j < s[i].length(); j++) {
  78.                                 assert((('a' <= s[i].charAt(j)) && (s[i].charAt(j) <= 'z')) || (s[i].charAt(j) == '.'));
  79.                                 fl = fl || s[i].charAt(j) == '.';
  80.                         }
  81.                         assert(fl);
  82.                 }
  83.                 ArrayDeque<Integer>[] l = new ArrayDeque[n];
  84.                 ArrayDeque<Long>[] h = new ArrayDeque[n];
  85.                 for (int i = 0; i < n; i++) {
  86.                         long tH = 0;
  87.                         int tL = 0;
  88.                         h[i] = new ArrayDeque<Long>();
  89.                         l[i] = new ArrayDeque<Integer>();
  90.                         for (int j = 0; j < s[i].length(); j++) {
  91.                                 if (s[i].charAt(j) == '.') {
  92.                                         if ((tH != 0) || (h[i].size() == 0)) {
  93.                                                 h[i].add(tH);
  94.                                                 if (!voc.contains(tH))
  95.                                                         badCount++;
  96.                                                 l[i].add(tL);
  97.                                                 tL = 0;
  98.                                                 tH = 0;
  99.                                         }
  100.                                 } else {
  101.                                         tH = tH * C1 + s[i].charAt(j);
  102.                                         tL++;
  103.                                 }
  104.                         }
  105.                         if ((l[i].size() == 0) || (l[i].getLast() != 0) || (tL > 0)) {
  106.                                 l[i].add(tL);
  107.                                 h[i].add(tH);
  108.                                 if (!voc.contains(tH))
  109.                                         badCount++;
  110.                         }
  111.                 }
  112.                 long[] pow = new long[s[0].length() + 10];
  113.                 pow[0] = 1;
  114.                 for (int i = 1; i < pow.length; i++) {
  115.                         pow[i] = pow[i - 1] * C1;
  116.                 }
  117.                 ArrayList<Integer> ans = new ArrayList<Integer>();
  118.                 for (int i = 0; i < n; i++) {
  119.                         if (!voc.contains(h[i].getFirst()))
  120.                                 badCount--;
  121.                         if ((!voc.contains(h[i].getLast())) && (h[i].size() > 1))
  122.                                 badCount--;
  123.                 }
  124.                 for (int i = 0; i < s[0].length(); i++) {
  125.                         if ((check(voc, n, h, l, pow)) && (badCount == 0))
  126.                                 ans.add(i);
  127.                         for (int j = 0; j < n; j++) {
  128.                                 if (s[j].charAt(i) != '.') {
  129.                                         h[j].addLast(h[j].removeLast() * C1 + s[j].charAt(i));
  130.                                         h[j].addFirst(h[j].removeFirst() - s[j].charAt(i)
  131.                                                         * pow[l[j].getFirst() - 1]);
  132.                                         l[j].addLast(l[j].removeLast() + 1);
  133.                                         l[j].addFirst(l[j].removeFirst() - 1);
  134.  
  135.                                 } else {
  136.                                         if ((l[j].getFirst() == 0) && (s[j].charAt((i + 1 ) % s[j].length()) != '.')) {
  137.                                                 l[j].removeFirst();
  138.                                                 h[j].removeFirst();
  139.                                                 if ((h[j].size() > 0) && (!voc.contains(h[j].getFirst())))
  140.                                                         badCount--;
  141.                                         }
  142.                                         if ((l[j].size() == 0) || (l[j].getLast() != 0)) {
  143.                                                 if ((h[j].size() > 0) && (!voc.contains(h[j].getLast())))
  144.                                                         badCount++;
  145.                                                 l[j].addLast(0);
  146.                                                 h[j].addLast((long) 0);
  147.                                         }
  148.                                 }
  149.                         }
  150.                 }
  151.                 out.println(ans.size());
  152.                 for (int i = 0; i < ans.size(); i++) {
  153.                         out.print(ans.get(i));
  154.                         if (i < ans.size() - 1)
  155.                                 out.print(' ');
  156.                         else
  157.                                 out.println();
  158.                 }
  159.         }
  160.  
  161.         public void run() {
  162.                 try {
  163.                         br = new BufferedReader(new InputStreamReader(System.in));
  164.                         out = new PrintWriter(System.out);
  165.  
  166. //                      br = new BufferedReader(new FileReader("eticket.in"));
  167. //                      out = new PrintWriter("eticket.out");
  168.  
  169.                         solve();
  170.  
  171.                         out.close();
  172.                 } catch (IOException e) {
  173.                         e.printStackTrace();
  174.                 }
  175.         }
  176.  
  177.         public static void main(String[] args) {
  178.                 new eticket_pk().run();
  179.         }
  180. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top