niyaznigmatullin

Untitled

Nov 10th, 2013
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.46 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4.  
  5. public class G {
  6.  
  7.     static void fft(double[] a, double[] b, int n, boolean inv) {
  8.         int bits = Integer.numberOfTrailingZeros(n);
  9.         for (int i = 0; i < n; i++) {
  10.             int j = Integer.reverse(i) >>> 32 - bits;
  11.             if (i < j) {
  12.                 double t = a[i];
  13.                 a[i] = a[j];
  14.                 a[j] = t;
  15.                 t = b[i];
  16.                 b[i] = b[j];
  17.                 b[j] = t;
  18.             }
  19.         }
  20.         for (int len = 2; len <= n; len <<= 1) {
  21.             int half = len >> 1;
  22.             double ang = 2 * Math.PI / len;
  23.             if (inv)
  24.                 ang = -ang;
  25.             double wmx = Math.cos(ang);
  26.             double wmy = Math.sin(ang);
  27.             for (int i = 0; i < n; i += len) {
  28.                 double wx = 1;
  29.                 double wy = 0;
  30.                 for (int j = 0; j < half; j++) {
  31.                     double ax = a[i + j];
  32.                     double ay = b[i + j];
  33.                     double bx = a[i + j + half];
  34.                     double by = b[i + j + half];
  35.                     double cx = bx * wx - by * wy;
  36.                     double cy = bx * wy + wx * by;
  37.                     a[i + j] = ax + cx;
  38.                     b[i + j] = ay + cy;
  39.                     a[i + j + half] = ax - cx;
  40.                     b[i + j + half] = ay - cy;
  41.                     double wnx = wx * wmx - wmy * wy;
  42.                     double wny = wx * wmy + wmx * wy;
  43.                     wx = wnx;
  44.                     wy = wny;
  45.                 }
  46.             }
  47.         }
  48.         if (inv) {
  49.             for (int i = 0; i < n; i++) {
  50.                 a[i] /= n;
  51.                 b[i] /= n;
  52.             }
  53.         }
  54.     }
  55.  
  56.     static void solve() throws IOException {
  57.         int n = nextInt();
  58.         int m = nextInt();
  59.         int[] a1 = new int[n];
  60.         int[] b1 = new int[n];
  61.         int[] a2 = new int[m];
  62.         int[] b2 = new int[m];
  63.         for (int i = 0; i < n; i++) {
  64.             String s = next();
  65.             a1[i] = Integer.parseInt(s.substring(0, s.length() - 1), 2);
  66.             b1[i] = s.charAt(s.length() - 1) - '0';
  67.         }
  68.         for (int i = 0; i < m; i++) {
  69.             String s = next();
  70.             a2[i] = Integer.parseInt(s.substring(0, s.length() - 1), 2);
  71.             b2[i] = s.charAt(s.length() - 1) - '0';
  72.         }
  73.         final int N = 1 << 19;
  74.         double[] x1 = new double[N];
  75.         double[] y1 = new double[N];
  76.         double[] x2 = new double[N];
  77.         double[] y2 = new double[N];
  78.         for (int i = 0; i < n; i++) {
  79.             if (b1[i] == 0) {
  80.                 x1[i] = 1;
  81.             } else {
  82.                 y1[i] = 1;
  83.             }
  84.         }
  85.         for (int i = 0; i < m; i++) {
  86.             if (b2[m - i - 1] == 1) {
  87.                 x2[i] = 1;
  88.             } else {
  89.                 y2[i] = 1;
  90.             }
  91.         }
  92.         fft(x1, y1, N, false);
  93.         fft(x2, y2, N, false);
  94.         for (int i = 0; i < N; i++) {
  95.             double x = x1[i] * x2[i] - y1[i] * y2[i];
  96.             double y = x1[i] * y2[i] + x2[i] * y1[i];
  97.             x1[i] = x;
  98.             y1[i] = y;
  99.         }      
  100.         fft(x1, y1, N, true);
  101.         int[] p = new int[m];
  102.         int k = -1;
  103.         p[0] = -1;
  104.         for (int i = 1; i < m; i++) {
  105.             while (k > -1 && a2[i] != a2[k + 1]) {
  106.                 k = p[k];
  107.             }
  108.             if (a2[k + 1] == a2[i]) {
  109.                 k++;
  110.             }
  111.             p[i] = k;
  112.         }
  113.         k = -1;
  114.         int id = -1;
  115.         int best = Integer.MAX_VALUE;
  116.         for (int i = 0; i < n; i++) {
  117.             while (k > -1 && (k + 1 >= m || a1[i] != a2[k + 1])) {
  118.                 k = p[k];
  119.             }
  120.             if (k + 1 < m && a1[i] == a2[k + 1]) {
  121.                 ++k;
  122.             }
  123.             if (k == m - 1) {
  124.                 int start = i - k;
  125.                 int count = m - (int) Math.round(y1[m + start - 1]);
  126.                 if (count < best) {
  127.                     best = count;
  128.                     id = start;
  129.                 }
  130.             }
  131.         }
  132.         if (id < 0) {
  133.             out.println("No");
  134.             return;
  135.         }
  136.         out.println("Yes");
  137.         out.println(best + " " + (id + 1));
  138.     }
  139.  
  140.     static StringTokenizer tokenizer;
  141.     static BufferedReader reader;
  142.     static PrintWriter out;
  143.  
  144.     public static void main(String[] args) throws IOException {
  145.         File file = new File("g.in");
  146.         InputStream input = System.in;
  147.         PrintStream output = System.out;
  148.         if (file.exists() && file.canRead()) {
  149.             input = new FileInputStream(file);
  150.         }
  151.         reader = new BufferedReader(new InputStreamReader(input));
  152.         out = new PrintWriter(output);
  153.         solve();
  154.         out.close();
  155.         reader.close();
  156.     }
  157.  
  158.     static String next() throws IOException {
  159.         while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  160.             String line = reader.readLine();
  161.             if (line == null) {
  162.                 return null;
  163.             }
  164.             tokenizer = new StringTokenizer(line);
  165.         }
  166.         return tokenizer.nextToken();
  167.     }
  168.  
  169.     static int nextInt() throws IOException {
  170.         return Integer.parseInt(next());
  171.     }
  172.  
  173.     static long nextLong() throws IOException {
  174.         return Long.parseLong(next());
  175.     }
  176.  
  177.     static double nextDouble() throws IOException {
  178.         return Double.parseDouble(next());
  179.     }
  180. }
Advertisement
Add Comment
Please, Sign In to add comment