fork download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.  
  7.     static class Lector {
  8.         private final BufferedInputStream entrada =
  9.             new BufferedInputStream(System.in);
  10.  
  11.         private final byte[] datos = new byte[65536];
  12.         private int actual = 0;
  13.         private int disponible = 0;
  14.  
  15.         private int obtener() throws IOException {
  16.             if (actual == disponible) {
  17.                 disponible = entrada.read(datos);
  18.                 actual = 0;
  19.  
  20.                 if (disponible == -1) return -1;
  21.             }
  22.  
  23.             return datos[actual++];
  24.         }
  25.  
  26.         int entero() throws IOException {
  27.             int c;
  28.  
  29.             do {
  30.                 c = obtener();
  31.                 if (c == -1) return -1;
  32.             } while (c <= 32);
  33.  
  34.             int valor = 0;
  35.  
  36.             while (c > 32) {
  37.                 valor = valor * 10 + c - 48;
  38.                 c = obtener();
  39.             }
  40.  
  41.             return valor;
  42.         }
  43.  
  44.         String cadena() throws IOException {
  45.             StringBuilder sb = new StringBuilder();
  46.             int c;
  47.  
  48.             do {
  49.                 c = obtener();
  50.                 if (c == -1) return null;
  51.             } while (c <= 32);
  52.  
  53.             while (c > 32) {
  54.                 sb.append((char) c);
  55.                 c = obtener();
  56.             }
  57.  
  58.             return sb.toString();
  59.         }
  60.     }
  61.  
  62.     static int[] crearOrden(int[] datos) {
  63.         int n = datos.length;
  64.  
  65.         int[] orden = new int[n];
  66.         int[] clase = new int[n];
  67.         int[] temporal = new int[n];
  68.         int[] siguienteClase = new int[n];
  69.  
  70.         int mayor = 0;
  71.  
  72.         for (int x : datos) {
  73.             if (x > mayor) mayor = x;
  74.         }
  75.  
  76.         int[] cuenta = new int[Math.max(n, mayor + 1)];
  77.  
  78.         for (int x : datos) {
  79.             cuenta[x]++;
  80.         }
  81.  
  82.         for (int i = 1; i <= mayor; i++) {
  83.             cuenta[i] += cuenta[i - 1];
  84.         }
  85.  
  86.         for (int i = n - 1; i >= 0; i--) {
  87.             orden[--cuenta[datos[i]]] = i;
  88.         }
  89.  
  90.         int grupos = 1;
  91.         clase[orden[0]] = 0;
  92.  
  93.         for (int i = 1; i < n; i++) {
  94.             if (datos[orden[i]] != datos[orden[i - 1]]) {
  95.                 grupos++;
  96.             }
  97.  
  98.             clase[orden[i]] = grupos - 1;
  99.         }
  100.  
  101.         for (int salto = 1; salto < n; salto <<= 1) {
  102.  
  103.             for (int i = 0; i < n; i++) {
  104.                 int p = orden[i] - salto;
  105.                 temporal[i] = p < 0 ? p + n : p;
  106.             }
  107.  
  108.             Arrays.fill(cuenta, 0, grupos, 0);
  109.  
  110.             for (int i = 0; i < n; i++) {
  111.                 cuenta[clase[temporal[i]]]++;
  112.             }
  113.  
  114.             for (int i = 1; i < grupos; i++) {
  115.                 cuenta[i] += cuenta[i - 1];
  116.             }
  117.  
  118.             for (int i = n - 1; i >= 0; i--) {
  119.                 int p = temporal[i];
  120.                 orden[--cuenta[clase[p]]] = p;
  121.             }
  122.  
  123.             siguienteClase[orden[0]] = 0;
  124.  
  125.             int nuevosGrupos = 1;
  126.  
  127.             for (int i = 1; i < n; i++) {
  128.                 int a = orden[i];
  129.                 int b = orden[i - 1];
  130.  
  131.                 int a2 = a + salto;
  132.                 int b2 = b + salto;
  133.  
  134.                 if (a2 >= n) a2 -= n;
  135.                 if (b2 >= n) b2 -= n;
  136.  
  137.                 if (clase[a] != clase[b] ||
  138.                     clase[a2] != clase[b2]) {
  139.                     nuevosGrupos++;
  140.                 }
  141.  
  142.                 siguienteClase[a] = nuevosGrupos - 1;
  143.             }
  144.  
  145.             int[] cambio = clase;
  146.             clase = siguienteClase;
  147.             siguienteClase = cambio;
  148.  
  149.             grupos = nuevosGrupos;
  150.  
  151.             if (grupos == n) break;
  152.         }
  153.  
  154.         return orden;
  155.     }
  156.  
  157.     static int[] obtenerLCP(int[] datos, int[] orden) {
  158.         int n = datos.length;
  159.  
  160.         int[] rango = new int[n];
  161.         int[] comun = new int[n];
  162.  
  163.         for (int i = 0; i < n; i++) {
  164.             rango[orden[i]] = i;
  165.         }
  166.  
  167.         int k = 0;
  168.  
  169.         for (int i = 0; i < n; i++) {
  170.             int posicion = rango[i];
  171.  
  172.             if (posicion == 0) {
  173.                 k = 0;
  174.                 continue;
  175.             }
  176.  
  177.             int anterior = orden[posicion - 1];
  178.  
  179.             while (i + k < n &&
  180.                    anterior + k < n &&
  181.                    datos[i + k] == datos[anterior + k]) {
  182.                 k++;
  183.             }
  184.  
  185.             comun[posicion] = k;
  186.  
  187.             if (k > 0) k--;
  188.         }
  189.  
  190.         return comun;
  191.     }
  192.  
  193.     static int[] unirCadenas(String s, String t, int n) {
  194.         int[] resultado = new int[4 * n + 2];
  195.  
  196.         int baseT = 2 * n + 1;
  197.  
  198.         for (int i = 0; i < n; i++) {
  199.             int x = s.charAt(i) + 2;
  200.             int y = t.charAt(i) + 2;
  201.  
  202.             resultado[i] = x;
  203.             resultado[i + n] = x;
  204.  
  205.             resultado[baseT + i] = y;
  206.             resultado[baseT + n + i] = y;
  207.         }
  208.  
  209.         resultado[2 * n] = 1;
  210.         resultado[4 * n + 1] = 0;
  211.  
  212.         return resultado;
  213.     }
  214.  
  215.     static long calcularRespuesta(
  216.         int n,
  217.         int[] orden,
  218.         int[] comun
  219.     ) {
  220.         int baseT = 2 * n + 1;
  221.  
  222.         int cantidadS = 0;
  223.         int cantidadT = 0;
  224.  
  225.         int ultimo = -1;
  226.         int minimo = Integer.MAX_VALUE;
  227.  
  228.         long anterioresS = 0;
  229.         long resultado = 0;
  230.  
  231.         for (int i = 0; i < orden.length; i++) {
  232.  
  233.             if (ultimo != -1) {
  234.                 minimo = Math.min(minimo, comun[i]);
  235.             }
  236.  
  237.             int p = orden[i];
  238.  
  239.             boolean perteneceS = p < n;
  240.  
  241.             boolean perteneceT =
  242.                 p >= baseT && p < baseT + n;
  243.  
  244.             if (!perteneceS && !perteneceT) {
  245.                 continue;
  246.             }
  247.  
  248.             if (ultimo == -1 || minimo < n) {
  249.  
  250.                 resultado += anterioresS * cantidadT;
  251.                 resultado += (long) cantidadS * cantidadT;
  252.  
  253.                 anterioresS += cantidadS;
  254.  
  255.                 cantidadS = 0;
  256.                 cantidadT = 0;
  257.             }
  258.  
  259.             if (perteneceS) {
  260.                 cantidadS++;
  261.             } else {
  262.                 cantidadT++;
  263.             }
  264.  
  265.             ultimo = i;
  266.             minimo = Integer.MAX_VALUE;
  267.         }
  268.  
  269.         resultado += anterioresS * cantidadT;
  270.         resultado += (long) cantidadS * cantidadT;
  271.  
  272.         return resultado;
  273.     }
  274.  
  275.     static long ejecutar(int n, String s, String t) {
  276.         int[] texto = unirCadenas(s, t, n);
  277.  
  278.         int[] orden = crearOrden(texto);
  279.  
  280.         int[] comun = obtenerLCP(texto, orden);
  281.  
  282.         return calcularRespuesta(n, orden, comun);
  283.     }
  284.  
  285.     public static void main(String[] args) throws IOException {
  286.         Lector entrada = new Lector();
  287.  
  288.         int n = entrada.entero();
  289.  
  290.         if (n < 1) return;
  291.  
  292.         String s = entrada.cadena();
  293.         String t = entrada.cadena();
  294.  
  295.         if (s == null || t == null ||
  296.             s.length() != n || t.length() != n) {
  297.             return;
  298.         }
  299.  
  300.         System.out.println(ejecutar(n, s, t));
  301.     }
  302. }
Success #stdin #stdout 0.08s 52772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MrDv63
language:
Java (12.0.1)
created:
1 day ago
visibility:
public

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!