█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 2074

Problema 0x43 - Encontrar el borde más largo de una string

  • Autor: Javier
  • Fecha: 2020-11-21 00:37:43 UTC (Hace más de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.007 s 1 KBi
#2
Correcto
0.013 s 1 KBi
#3
Correcto
0.009 s 1 KBi
#4
Correcto
0.008 s 9 KBi
#5
Correcto
0.006 s 7 KBi
#6
Correcto
0.007 s 1 KBi
#7
Correcto
0.013 s 2 KBi
#8
Correcto
0.014 s 2 KBi
#9
Correcto
0.013 s 2 KBi
#10
Correcto
0.013 s 2 KBi
#11
Correcto
0.014 s 2 KBi
#12
Correcto
0.013 s 2 KBi
#13
Correcto
0.015 s 2 KBi
#14
Correcto
0.013 s 2 KBi
#15
Correcto
0.012 s 2 KBi
#16
Correcto
0.016 s 2 KBi
#17
Correcto
0.014 s 2 KBi
#18
Correcto
0.014 s 2 KBi
#19
Correcto
0.015 s 2 KBi
#20
Correcto
0.012 s 2 KBi
#21
Correcto
0.015 s 2 KBi
#22
Correcto
0.03 s 2 KBi
Puntos totales: 100 / 100

Código

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  string input;
  cin >> input;
  vector<int> prefix (input.length(), 0);
  int border = 0;
  for (int i = 1; i < input.length(); i++) {
	 while(border>0 and input[i] != input[border]) {
		border = prefix[border-1];
	 }
	 if (input[i] == input[border]) {
		border++;
	 } else {
		border = 0;
	 }
	 prefix[i] = border;
  }
  cout << prefix[input.length()-1] << endl;
  return 0;
}