fork download
copy 
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.*;
  4.  
  5. class CyclicHashes implements Runnable {
  6.  
  7.     private BufferedReader in;
  8.     private PrintWriter out;
  9.  
  10.     void init() throws FileNotFoundException {
  11.         in = new BufferedReader(new InputStreamReader(System.in));
  12.         out = new PrintWriter(System.out);
  13.     }
  14.  
  15.     public static void main(String[] args) {
  16.         new Thread(null, new CyclicHashes(), "", 1l * 200 * 1024 * 1024).start();
  17.     }
  18.  
  19.     public void run() {
  20.         try {
  21.             init();
  22.             solve();
  23.             out.close();
  24.         } catch (Exception e) {
  25.             e.printStackTrace();
  26.             System.exit(-1);
  27.         }
  28.     }
  29.  
  30.     int n;
  31.     int prime1;
  32.     int mod1;
  33.     int[] pow1;
  34.     int[] h1;
  35.  
  36.     void init(char[] s) {
  37.         Random rnd = new Random();
  38.         prime1 = BigInteger.valueOf(3000 + rnd.nextInt(500))
  39.                 .nextProbablePrime().intValue();
  40.         mod1 = BigInteger.valueOf((int) 1e9 + rnd.nextInt(500))
  41.                 .nextProbablePrime().intValue();
  42.         n = s.length;
  43.         pow1 = new int[n];
  44.         pow1[0] = 1;
  45.         for (int i = 1; i < n; i++) {
  46.             pow1[i] = (int) ((long) pow1[i - 1] * prime1 % mod1);
  47.         }
  48.         h1 = new int[n];
  49.         h1[0] = s[0];
  50.         for (int i = 1; i < n; i++) {
  51.             h1[i] = (int) ((h1[i - 1] + (long) pow1[i] * s[i]) % mod1);
  52.         }
  53.     }
  54.  
  55.     int getHash(int L, int R, int[] h, int[] pow, int mod) {
  56.         int hash = h[R];
  57.         if (L > 0)
  58.             hash -= h[L - 1];
  59.         if (hash < 0)
  60.             hash += mod;
  61.         return (int) ((long) hash * pow[n - R - 1] % mod);
  62.     }
  63.  
  64.     boolean equals(int L1, int R1, int L2, int R2) {
  65.         long hash1 = getHash(L1, R1, h1, pow1, mod1);
  66.         long hash2 = getHash(L2, R2, h1, pow1, mod1);
  67.         return hash1 == hash2;
  68.     }
  69.  
  70.     void solve() throws IOException {
  71.         int n = Integer.parseInt(in.readLine());
  72.         String s = in.readLine();
  73.         String t = in.readLine();
  74.         StringBuilder sb = new StringBuilder();
  75.         sb.append(s);
  76.         sb.append(t);
  77.         sb.append(t);
  78.         char[] res = sb.toString().toCharArray();
  79.  
  80.         init(res);
  81.  
  82.         for (int shift = 0; shift < n; shift++) {
  83.             if (equals(0, n - 1, n + shift, 2 * n - 1 + shift)) {
  84.                 out.println(shift);
  85.                 return;
  86.             }
  87.         }
  88.         out.println(-1);
  89.  
  90.     }
  91.  
  92. }
Success #stdin #stdout 0.05s 320704KB
comments (?)
stdin
copy 
11
abracadabra
racadabraab
stdout
copy 
9
https://ideone.com/zBAMZh
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!