Advertisement
raliev

Untitled

May 29th, 2012
910
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.63 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement