fork download
copy 
  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[] datos = new byte[1 << 16];
  12.         private int pos = 0;
  13.         private int longitud = 0;
  14.  
  15.         private int leer() throws IOException {
  16.             if (pos >= longitud) {
  17.                 longitud = entrada.read(datos);
  18.                 pos = 0;
  19.  
  20.                 if (longitud <= 0) return -1;
  21.             }
  22.  
  23.             return datos[pos++];
  24.         }
  25.  
  26.         String leerCadena() throws IOException {
  27.             StringBuilder texto = new StringBuilder();
  28.             int caracter;
  29.  
  30.             do {
  31.                 caracter = leer();
  32.                 if (caracter == -1) return null;
  33.             } while (caracter <= 32);
  34.  
  35.             while (caracter > 32) {
  36.                 texto.append((char) caracter);
  37.                 caracter = leer();
  38.             }
  39.  
  40.             return texto.toString();
  41.         }
  42.  
  43.         int leerEntero() throws IOException {
  44.             int caracter;
  45.  
  46.             do {
  47.                 caracter = leer();
  48.                 if (caracter == -1) return -1;
  49.             } while (caracter <= 32);
  50.  
  51.             int valor = 0;
  52.  
  53.             while (caracter > 32) {
  54.                 valor = valor * 10 + caracter - '0';
  55.                 caracter = leer();
  56.             }
  57.  
  58.             return valor;
  59.         }
  60.     }
  61.  
  62.     static int[] construirSufijos(int[] texto) {
  63.         int n = texto.length;
  64.  
  65.         int[] orden = new int[n];
  66.         int[] clase = new int[n];
  67.         int[] desplazados = new int[n];
  68.         int[] nuevaClase = new int[n];
  69.         int[] conteo = new int[Math.max(n, 28)];
  70.  
  71.         for (int valor : texto) {
  72.             conteo[valor]++;
  73.         }
  74.  
  75.         for (int i = 1; i < 28; i++) {
  76.             conteo[i] += conteo[i - 1];
  77.         }
  78.  
  79.         for (int i = n - 1; i >= 0; i--) {
  80.             orden[--conteo[texto[i]]] = i;
  81.         }
  82.  
  83.         int clases = 1;
  84.         clase[orden[0]] = 0;
  85.  
  86.         for (int i = 1; i < n; i++) {
  87.             if (texto[orden[i]] != texto[orden[i - 1]]) {
  88.                 clases++;
  89.             }
  90.  
  91.             clase[orden[i]] = clases - 1;
  92.         }
  93.  
  94.         for (int salto = 1; salto < n; salto <<= 1) {
  95.  
  96.             for (int i = 0; i < n; i++) {
  97.                 desplazados[i] = orden[i] - salto;
  98.  
  99.                 if (desplazados[i] < 0) {
  100.                     desplazados[i] += n;
  101.                 }
  102.             }
  103.  
  104.             Arrays.fill(conteo, 0, clases, 0);
  105.  
  106.             for (int i = 0; i < n; i++) {
  107.                 conteo[clase[desplazados[i]]]++;
  108.             }
  109.  
  110.             for (int i = 1; i < clases; i++) {
  111.                 conteo[i] += conteo[i - 1];
  112.             }
  113.  
  114.             for (int i = n - 1; i >= 0; i--) {
  115.                 int actual = desplazados[i];
  116.                 int grupo = clase[actual];
  117.  
  118.                 orden[--conteo[grupo]] = actual;
  119.             }
  120.  
  121.             nuevaClase[orden[0]] = 0;
  122.  
  123.             int nuevasClases = 1;
  124.  
  125.             for (int i = 1; i < n; i++) {
  126.                 int actual = orden[i];
  127.                 int anterior = orden[i - 1];
  128.  
  129.                 int medioActual = (actual + salto) % n;
  130.                 int medioAnterior = (anterior + salto) % n;
  131.  
  132.                 if (clase[actual] != clase[anterior] ||
  133.                     clase[medioActual] != clase[medioAnterior]) {
  134.  
  135.                     nuevasClases++;
  136.                 }
  137.  
  138.                 nuevaClase[actual] = nuevasClases - 1;
  139.             }
  140.  
  141.             int[] temporal = clase;
  142.             clase = nuevaClase;
  143.             nuevaClase = temporal;
  144.  
  145.             clases = nuevasClases;
  146.  
  147.             if (clases == n) break;
  148.         }
  149.  
  150.         return orden;
  151.     }
  152.  
  153.     static int[] calcularLcp(int[] texto, int[] orden) {
  154.         int n = texto.length;
  155.  
  156.         int[] rango = new int[n];
  157.         int[] lcp = new int[n];
  158.  
  159.         for (int i = 0; i < n; i++) {
  160.             rango[orden[i]] = i;
  161.         }
  162.  
  163.         int comun = 0;
  164.  
  165.         for (int i = 0; i < n; i++) {
  166.             int posicion = rango[i];
  167.  
  168.             if (posicion == 0) {
  169.                 comun = 0;
  170.                 continue;
  171.             }
  172.  
  173.             int anterior = orden[posicion - 1];
  174.  
  175.             while (i + comun < n &&
  176.                    anterior + comun < n &&
  177.                    texto[i + comun] == texto[anterior + comun]) {
  178.  
  179.                 comun++;
  180.             }
  181.  
  182.             lcp[posicion] = comun;
  183.  
  184.             if (comun > 0) {
  185.                 comun--;
  186.             }
  187.         }
  188.  
  189.         return lcp;
  190.     }
  191.  
  192.     static long resolver(int n, String cadenaS, String cadenaT) {
  193.  
  194.         int total = 4 * n + 2;
  195.         int inicioT = 2 * n + 1;
  196.  
  197.         int[] texto = new int[total];
  198.  
  199.         for (int i = 0; i < n; i++) {
  200.             int letraS = cadenaS.charAt(i) - 'a' + 2;
  201.             int letraT = cadenaT.charAt(i) - 'a' + 2;
  202.  
  203.             texto[i] = letraS;
  204.             texto[i + n] = letraS;
  205.  
  206.             texto[inicioT + i] = letraT;
  207.             texto[inicioT + n + i] = letraT;
  208.         }
  209.  
  210.         texto[2 * n] = 1;
  211.         texto[total - 1] = 0;
  212.  
  213.         int[] orden = construirSufijos(texto);
  214.         int[] lcp = calcularLcp(texto, orden);
  215.  
  216.         long respuesta = 0;
  217.         long vistosS = 0;
  218.  
  219.         int cantidadS = 0;
  220.         int cantidadT = 0;
  221.  
  222.         int anteriorValido = -1;
  223.         int minimoComun = Integer.MAX_VALUE;
  224.  
  225.         for (int i = 0; i < total; i++) {
  226.  
  227.             if (anteriorValido != -1 && i > anteriorValido) {
  228.                 minimoComun = Math.min(minimoComun, lcp[i]);
  229.             }
  230.  
  231.             int posicion = orden[i];
  232.  
  233.             boolean esS = posicion < n;
  234.  
  235.             boolean esT = posicion >= inicioT &&
  236.                           posicion < inicioT + n;
  237.  
  238.             if (!esS && !esT) {
  239.                 continue;
  240.             }
  241.  
  242.             if (anteriorValido == -1 || minimoComun < n) {
  243.  
  244.                 if (anteriorValido != -1) {
  245.                     respuesta += vistosS * cantidadT +
  246.                                  (long) cantidadS * cantidadT;
  247.  
  248.                     vistosS += cantidadS;
  249.                 }
  250.  
  251.                 cantidadS = 0;
  252.                 cantidadT = 0;
  253.             }
  254.  
  255.             if (esS) {
  256.                 cantidadS++;
  257.             } else {
  258.                 cantidadT++;
  259.             }
  260.  
  261.             anteriorValido = i;
  262.             minimoComun = Integer.MAX_VALUE;
  263.         }
  264.  
  265.         respuesta += vistosS * cantidadT +
  266.                      (long) cantidadS * cantidadT;
  267.  
  268.         return respuesta;
  269.     }
  270.  
  271.     public static void main(String[] args) throws IOException {
  272.  
  273.         EntradaRapida lector = new EntradaRapida();
  274.  
  275.         int n = lector.leerEntero();
  276.  
  277.         if (n == -1) return;
  278.  
  279.         String cadenaS = lector.leerCadena();
  280.         String cadenaT = lector.leerCadena();
  281.  
  282.         System.out.println(resolver(n, cadenaS, cadenaT));
  283.     }
  284. }
Success #stdin #stdout 0.07s 54816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/y4ObeR
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!