Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class G {
- static void fft(double[] a, double[] b, int n, boolean inv) {
- int bits = Integer.numberOfTrailingZeros(n);
- for (int i = 0; i < n; i++) {
- int j = Integer.reverse(i) >>> 32 - bits;
- if (i < j) {
- double t = a[i];
- a[i] = a[j];
- a[j] = t;
- t = b[i];
- b[i] = b[j];
- b[j] = t;
- }
- }
- for (int len = 2; len <= n; len <<= 1) {
- int half = len >> 1;
- double ang = 2 * Math.PI / len;
- if (inv)
- ang = -ang;
- double wmx = Math.cos(ang);
- double wmy = Math.sin(ang);
- for (int i = 0; i < n; i += len) {
- double wx = 1;
- double wy = 0;
- for (int j = 0; j < half; j++) {
- double ax = a[i + j];
- double ay = b[i + j];
- double bx = a[i + j + half];
- double by = b[i + j + half];
- double cx = bx * wx - by * wy;
- double cy = bx * wy + wx * by;
- a[i + j] = ax + cx;
- b[i + j] = ay + cy;
- a[i + j + half] = ax - cx;
- b[i + j + half] = ay - cy;
- double wnx = wx * wmx - wmy * wy;
- double wny = wx * wmy + wmx * wy;
- wx = wnx;
- wy = wny;
- }
- }
- }
- if (inv) {
- for (int i = 0; i < n; i++) {
- a[i] /= n;
- b[i] /= n;
- }
- }
- }
- static void solve() throws IOException {
- int n = nextInt();
- int m = nextInt();
- int[] a1 = new int[n];
- int[] b1 = new int[n];
- int[] a2 = new int[m];
- int[] b2 = new int[m];
- for (int i = 0; i < n; i++) {
- String s = next();
- a1[i] = Integer.parseInt(s.substring(0, s.length() - 1), 2);
- b1[i] = s.charAt(s.length() - 1) - '0';
- }
- for (int i = 0; i < m; i++) {
- String s = next();
- a2[i] = Integer.parseInt(s.substring(0, s.length() - 1), 2);
- b2[i] = s.charAt(s.length() - 1) - '0';
- }
- final int N = 1 << 19;
- double[] x1 = new double[N];
- double[] y1 = new double[N];
- double[] x2 = new double[N];
- double[] y2 = new double[N];
- for (int i = 0; i < n; i++) {
- if (b1[i] == 0) {
- x1[i] = 1;
- } else {
- y1[i] = 1;
- }
- }
- for (int i = 0; i < m; i++) {
- if (b2[m - i - 1] == 1) {
- x2[i] = 1;
- } else {
- y2[i] = 1;
- }
- }
- fft(x1, y1, N, false);
- fft(x2, y2, N, false);
- for (int i = 0; i < N; i++) {
- double x = x1[i] * x2[i] - y1[i] * y2[i];
- double y = x1[i] * y2[i] + x2[i] * y1[i];
- x1[i] = x;
- y1[i] = y;
- }
- fft(x1, y1, N, true);
- int[] p = new int[m];
- int k = -1;
- p[0] = -1;
- for (int i = 1; i < m; i++) {
- while (k > -1 && a2[i] != a2[k + 1]) {
- k = p[k];
- }
- if (a2[k + 1] == a2[i]) {
- k++;
- }
- p[i] = k;
- }
- k = -1;
- int id = -1;
- int best = Integer.MAX_VALUE;
- for (int i = 0; i < n; i++) {
- while (k > -1 && (k + 1 >= m || a1[i] != a2[k + 1])) {
- k = p[k];
- }
- if (k + 1 < m && a1[i] == a2[k + 1]) {
- ++k;
- }
- if (k == m - 1) {
- int start = i - k;
- int count = m - (int) Math.round(y1[m + start - 1]);
- if (count < best) {
- best = count;
- id = start;
- }
- }
- }
- if (id < 0) {
- out.println("No");
- return;
- }
- out.println("Yes");
- out.println(best + " " + (id + 1));
- }
- static StringTokenizer tokenizer;
- static BufferedReader reader;
- static PrintWriter out;
- public static void main(String[] args) throws IOException {
- File file = new File("g.in");
- InputStream input = System.in;
- PrintStream output = System.out;
- if (file.exists() && file.canRead()) {
- input = new FileInputStream(file);
- }
- reader = new BufferedReader(new InputStreamReader(input));
- out = new PrintWriter(output);
- solve();
- out.close();
- reader.close();
- }
- static String next() throws IOException {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- String line = reader.readLine();
- if (line == null) {
- return null;
- }
- tokenizer = new StringTokenizer(line);
- }
- return tokenizer.nextToken();
- }
- static int nextInt() throws IOException {
- return Integer.parseInt(next());
- }
- static long nextLong() throws IOException {
- return Long.parseLong(next());
- }
- static double nextDouble() throws IOException {
- return Double.parseDouble(next());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment