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