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, prime2;
  32.     int mod1, mod2;
  33.     int[] pow1, pow2;
  34.     int[] h1, h2;
  35.  
  36.     void init(char[] s) {
  37.         Random rnd = new Random();
  38.         prime1 = BigInteger.valueOf(3000 + rnd.nextInt(500))
  39.                 .nextProbablePrime().intValue();
  40.         prime2 = BigInteger.valueOf(4000 + rnd.nextInt(500))
  41.                 .nextProbablePrime().intValue();
  42.         mod1 = BigInteger.valueOf((int) 1e9 + rnd.nextInt(500))
  43.                 .nextProbablePrime().intValue();
  44.         mod2 = BigInteger.valueOf((int) 1e9 + (int) 1e6 + rnd.nextInt(500))
  45.                 .nextProbablePrime().intValue();
  46.         n = s.length;
  47.         pow1 = new int[n];
  48.         pow2 = new int[n];
  49.         pow1[0] = pow2[0] = 1;
  50.         for (int i = 1; i < n; i++) {
  51.             pow1[i] = (int) ((long) pow1[i - 1] * prime1 % mod1);
  52.             pow2[i] = (int) ((long) pow2[i - 1] * prime2 % mod2);
  53.         }
  54.         h1 = new int[n];
  55.         h2 = new int[n];
  56.         h1[0] = h2[0] = s[0];
  57.         for (int i = 1; i < n; i++) {
  58.             h1[i] = (int) ((h1[i - 1] + (long) pow1[i] * s[i]) % mod1);
  59.             h2[i] = (int) ((h2[i - 1] + (long) pow2[i] * s[i]) % mod2);
  60.         }
  61.     }
  62.  
  63.     long getHash(int L, int R) {
  64.         int hash1 = getHash(L, R, h1, pow1, mod1);
  65.         int hash2 = getHash(L, R, h2, pow2, mod2);
  66.         return ((long) hash1 << 32) | hash2;
  67.     }
  68.  
  69.     int getHash(int L, int R, int[] h, int[] pow, int mod) {
  70.         int hash = h[R];
  71.         if (L > 0)
  72.             hash -= h[L - 1];
  73.         if (hash < 0)
  74.             hash += mod;
  75.         return (int) ((long) hash * pow[n - R - 1] % mod);
  76.     }
  77.  
  78.     boolean equals(int L1, int R1, int L2, int R2) {
  79.         long hash1 = getHash(L1, R1);
  80.         long hash2 = getHash(L2, R2);
  81.         return hash1 == hash2;
  82.     }
  83.  
  84.     void solve() throws IOException {
  85.         int n = Integer.parseInt(in.readLine());
  86.         String s = in.readLine();
  87.         String t = in.readLine();
  88.         StringBuilder sb = new StringBuilder();
  89.         sb.append(s);
  90.         sb.append(t);
  91.         sb.append(t);
  92.         char[] res = sb.toString().toCharArray();
  93.  
  94.         init(res);
  95.  
  96.         for (int shift = 0; shift < n; shift++) {
  97.             if (equals(0, n - 1, n + shift, 2 * n - 1 + shift)) {
  98.                 out.println(shift);
  99.                 return;
  100.             }
  101.         }
  102.         out.println(-1);
  103.  
  104.     }
  105.  
  106. }
Success #stdin #stdout 0.06s 320704KB
comments (?)
stdin
copy 
11
abracadabra
racadabraab
stdout
copy 
9
https://ideone.com/fAZQpx
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!