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

Envío 5373

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

  • Autor: alejopelaez
  • Fecha: 2021-12-03 23:30:31 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.003 s 0 KBi
#2
Correcto
0.004 s 0 KBi
#3
Correcto
0.004 s 0 KBi
#4
Correcto
0.005 s 0 KBi
#5
Correcto
0.004 s 0 KBi
#6
Correcto
0.004 s 0 KBi
#7
Correcto
0.007 s 0 KBi
#8
Correcto
0.006 s 1 KBi
#9
Correcto
0.008 s 0 KBi
#10
Correcto
0.009 s 0 KBi
#11
Correcto
0.01 s 0 KBi
#12
Correcto
0.008 s 0 KBi
#13
Tiempo límite excedido
1.068 s 0 KBi
#14
Tiempo límite excedido
1.06 s 0 KBi
#15
Tiempo límite excedido
1.081 s 0 KBi
#16
Tiempo límite excedido
1.092 s 0 KBi
#17
Correcto
0.009 s 0 KBi
#18
Correcto
0.009 s 0 KBi
#19
Correcto
0.013 s 0 KBi
#20
Correcto
0.012 s 0 KBi
#21
Correcto
0.011 s 0 KBi
#22
Correcto
0.012 s 0 KBi
Puntos totales: 82 / 100

Código

#include <iostream>
#include <string>
using namespace std;

// Random integer in the range [0, n]
size_t randomNumber(size_t n) {
  if (n <= 1) {
	  return 0;
  }
  return rand() % (n+1);
}

bool isBorder(const std::string& input, size_t lStart, size_t lEnd, size_t rStart, size_t rEnd) {
	// Check first and last
	if (input[lStart] != input[rStart]) {
		return false;
	}
	if (input[lEnd] != input[rEnd]) {
		return false;
	}
	// Generate 50 random points in the strings, and check if they are the same
	for (int j = 0; j < 50; ++j) {
		auto randPos = randomNumber(lEnd);
		if (input[randPos] != input[randPos+rStart]) {
			return false;
		}
	}
	// If we are here, the 10 random checks succeeeded, so let check the whole thing
	for (size_t offset = lStart; offset <= lEnd; ++offset) {
		if (input[offset] != input[offset+rStart]) {
			return false;
		}
	}
	return true;
}

int main() {
  srand((unsigned) time(NULL));
  std::string input;

  cin >> input;
  
  int32_t maxBorder = 0;
  for (size_t idx = 1; idx < input.size(); ++idx) {
	if (isBorder(input, 0, input.size() - idx - 1, idx, input.size()-1)) {
		maxBorder = input.size() - idx;
		break;
	}
  }
  
  cout << maxBorder;
  
  return 0;
}