fork download 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.  
  7.     static class EntradaRapida {
  8.         private final BufferedInputStream entrada =
  9.             new BufferedInputStream(System.in);
  10.  
  11.         private final byte[] buffer = new byte[1 << 16];
  12.         private int posicion = 0;
  13.         private int cantidad = 0;
  14.  
  15.         private int leer() throws IOException {
  16.             if (posicion >= cantidad) {
  17.                 cantidad = entrada.read(buffer);
  18.                 posicion = 0;
  19.  
  20.                 if (cantidad <= 0) return -1;
  21.             }
  22.  
  23.             return buffer[posicion++];
  24.         }
  25.  
  26.         int leerEntero() throws IOException {
  27.             int caracter;
  28.  
  29.             do {
  30.                 caracter = leer();
  31.                 if (caracter == -1) return -1;
  32.             } while (caracter <= 32);
  33.  
  34.             int numero = 0;
  35.  
  36.             while (caracter > 32) {
  37.                 numero = numero * 10 + caracter - '0';
  38.                 caracter = leer();
  39.             }
  40.  
  41.             return numero;
  42.         }
  43.  
  44.         String leerCadena() throws IOException {
  45.             StringBuilder resultado = new StringBuilder();
  46.             int caracter;
  47.  
  48.             do {
  49.                 caracter = leer();
  50.                 if (caracter == -1) return null;
  51.             } while (caracter <= 32);
  52.  
  53.             while (caracter > 32) {
  54.                 resultado.append((char) caracter);
  55.                 caracter = leer();
  56.             }
  57.  
  58.             return resultado.toString();
  59.         }
  60.     }
  61.  
  62.     static int[] construirSuffixArray(int[] texto) {
  63.         int longitud = texto.length;
  64.  
  65.         int[] sufijos = new int[longitud];
  66.         int[] clases = new int[longitud];
  67.         int[] auxiliar = new int[longitud];
  68.         int[] nuevasClases = new int[longitud];
  69.  
  70.         int maximoSimbolo = 0;
  71.  
  72.         for (int valor : texto) {
  73.             maximoSimbolo = Math.max(maximoSimbolo, valor);
  74.         }
  75.  
  76.         int[] frecuencias = new int[
  77.             Math.max(longitud, maximoSimbolo + 1)
  78.         ];
  79.  
  80.         for (int valor : texto) {
  81.             frecuencias[valor]++;
  82.         }
  83.  
  84.         for (int i = 1; i <= maximoSimbolo; i++) {
  85.             frecuencias[i] += frecuencias[i - 1];
  86.         }
  87.  
  88.         for (int i = longitud - 1; i >= 0; i--) {
  89.             sufijos[--frecuencias[texto[i]]] = i;
  90.         }
  91.  
  92.         int cantidadClases = 1;
  93.         clases[sufijos[0]] = 0;
  94.  
  95.         for (int i = 1; i < longitud; i++) {
  96.             if (texto[sufijos[i]] != texto[sufijos[i - 1]]) {
  97.                 cantidadClases++;
  98.             }
  99.  
  100.             clases[sufijos[i]] = cantidadClases - 1;
  101.         }
  102.  
  103.         for (int distancia = 1;
  104.              distancia < longitud;
  105.              distancia <<= 1) {
  106.  
  107.             for (int i = 0; i < longitud; i++) {
  108.                 auxiliar[i] = sufijos[i] - distancia;
  109.  
  110.                 if (auxiliar[i] < 0) {
  111.                     auxiliar[i] += longitud;
  112.                 }
  113.             }
  114.  
  115.             Arrays.fill(frecuencias, 0, cantidadClases, 0);
  116.  
  117.             for (int i = 0; i < longitud; i++) {
  118.                 frecuencias[clases[auxiliar[i]]]++;
  119.             }
  120.  
  121.             for (int i = 1; i < cantidadClases; i++) {
  122.                 frecuencias[i] += frecuencias[i - 1];
  123.             }
  124.  
  125.             for (int i = longitud - 1; i >= 0; i--) {
  126.                 int indice = auxiliar[i];
  127.                 int clase = clases[indice];
  128.  
  129.                 sufijos[--frecuencias[clase]] = indice;
  130.             }
  131.  
  132.             nuevasClases[sufijos[0]] = 0;
  133.  
  134.             int totalNuevasClases = 1;
  135.  
  136.             for (int i = 1; i < longitud; i++) {
  137.                 int actual = sufijos[i];
  138.                 int anterior = sufijos[i - 1];
  139.  
  140.                 int segundoActual = actual + distancia;
  141.                 int segundoAnterior = anterior + distancia;
  142.  
  143.                 if (segundoActual >= longitud) {
  144.                     segundoActual -= longitud;
  145.                 }
  146.  
  147.                 if (segundoAnterior >= longitud) {
  148.                     segundoAnterior -= longitud;
  149.                 }
  150.  
  151.                 if (clases[actual] != clases[anterior] ||
  152.                     clases[segundoActual] != clases[segundoAnterior]) {
  153.  
  154.                     totalNuevasClases++;
  155.                 }
  156.  
  157.                 nuevasClases[actual] = totalNuevasClases - 1;
  158.             }
  159.  
  160.             int[] intercambio = clases;
  161.             clases = nuevasClases;
  162.             nuevasClases = intercambio;
  163.  
  164.             cantidadClases = totalNuevasClases;
  165.  
  166.             if (cantidadClases == longitud) {
  167.                 break;
  168.             }
  169.         }
  170.  
  171.         return sufijos;
  172.     }
  173.  
  174.     static int[] construirLCP(int[] texto, int[] sufijos) {
  175.         int longitud = texto.length;
  176.  
  177.         int[] posiciones = new int[longitud];
  178.         int[] lcp = new int[longitud];
  179.  
  180.         for (int i = 0; i < longitud; i++) {
  181.             posiciones[sufijos[i]] = i;
  182.         }
  183.  
  184.         int compartidos = 0;
  185.  
  186.         for (int i = 0; i < longitud; i++) {
  187.             int rango = posiciones[i];
  188.  
  189.             if (rango == 0) {
  190.                 compartidos = 0;
  191.                 continue;
  192.             }
  193.  
  194.             int anterior = sufijos[rango - 1];
  195.  
  196.             while (i + compartidos < longitud &&
  197.                    anterior + compartidos < longitud &&
  198.                    texto[i + compartidos] ==
  199.                    texto[anterior + compartidos]) {
  200.  
  201.                 compartidos++;
  202.             }
  203.  
  204.             lcp[rango] = compartidos;
  205.  
  206.             if (compartidos > 0) {
  207.                 compartidos--;
  208.             }
  209.         }
  210.  
  211.         return lcp;
  212.     }
  213.  
  214.     static int[] construirTexto(
  215.         String cadenaS,
  216.         String cadenaT,
  217.         int n
  218.     ) {
  219.         int[] texto = new int[4 * n + 2];
  220.  
  221.         int inicioT = 2 * n + 1;
  222.  
  223.         for (int i = 0; i < n; i++) {
  224.             int simboloS = cadenaS.charAt(i) + 2;
  225.             int simboloT = cadenaT.charAt(i) + 2;
  226.  
  227.             texto[i] = simboloS;
  228.             texto[i + n] = simboloS;
  229.  
  230.             texto[inicioT + i] = simboloT;
  231.             texto[inicioT + n + i] = simboloT;
  232.         }
  233.  
  234.         texto[2 * n] = 1;
  235.         texto[4 * n + 1] = 0;
  236.  
  237.         return texto;
  238.     }
  239.  
  240.     static long contarPares(
  241.         int n,
  242.         int[] sufijos,
  243.         int[] lcp
  244.     ) {
  245.         int inicioT = 2 * n + 1;
  246.  
  247.         int grupoS = 0;
  248.         int grupoT = 0;
  249.  
  250.         int anteriorSeleccionado = -1;
  251.         int minimoLCP = Integer.MAX_VALUE;
  252.  
  253.         long acumuladoS = 0;
  254.         long respuesta = 0;
  255.  
  256.         for (int i = 0; i < sufijos.length; i++) {
  257.  
  258.             if (anteriorSeleccionado != -1) {
  259.                 minimoLCP = Math.min(minimoLCP, lcp[i]);
  260.             }
  261.  
  262.             int posicion = sufijos[i];
  263.  
  264.             boolean esS = posicion < n;
  265.  
  266.             boolean esT =
  267.                 posicion >= inicioT &&
  268.                 posicion < inicioT + n;
  269.  
  270.             if (!esS && !esT) {
  271.                 continue;
  272.             }
  273.  
  274.             if (anteriorSeleccionado == -1 ||
  275.                 minimoLCP < n) {
  276.  
  277.                 respuesta += acumuladoS * grupoT;
  278.                 respuesta += (long) grupoS * grupoT;
  279.  
  280.                 acumuladoS += grupoS;
  281.  
  282.                 grupoS = 0;
  283.                 grupoT = 0;
  284.             }
  285.  
  286.             if (esS) {
  287.                 grupoS++;
  288.             } else {
  289.                 grupoT++;
  290.             }
  291.  
  292.             anteriorSeleccionado = i;
  293.             minimoLCP = Integer.MAX_VALUE;
  294.         }
  295.  
  296.         respuesta += acumuladoS * grupoT;
  297.         respuesta += (long) grupoS * grupoT;
  298.  
  299.         return respuesta;
  300.     }
  301.  
  302.     static long resolver(
  303.         int n,
  304.         String cadenaS,
  305.         String cadenaT
  306.     ) {
  307.         int[] texto = construirTexto(cadenaS, cadenaT, n);
  308.  
  309.         int[] sufijos = construirSuffixArray(texto);
  310.  
  311.         int[] lcp = construirLCP(texto, sufijos);
  312.  
  313.         return contarPares(n, sufijos, lcp);
  314.     }
  315.  
  316.     public static void main(String[] args) throws IOException {
  317.         EntradaRapida lector = new EntradaRapida();
  318.  
  319.         int n = lector.leerEntero();
  320.  
  321.         if (n == -1) return;
  322.  
  323.         String cadenaS = lector.leerCadena();
  324.         String cadenaT = lector.leerCadena();
  325.  
  326.         if (cadenaS == null || cadenaT == null ||
  327.             cadenaS.length() != n || cadenaT.length() != n) {
  328.             return;
  329.         }
  330.  
  331.         System.out.println(resolver(n, cadenaS, cadenaT));
  332.     }
  333. }
Success #stdin #stdout 0.08s 16544KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/TJW6Ub
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!