Envío 3046

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

Autor: SeMeOlvidoLaContra
Fecha: 2021-02-16 20:18:50 UTC (Hace casi 4 años)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto	0.006 s	2 KBi
#2	Correcto	0.007 s	1 KBi
#3	Correcto	0.007 s	2 KBi
#4	Correcto	0.005 s	2 KBi
#5	Correcto	0.005 s	1 KBi
#6	Correcto	0.006 s	1 KBi
#7	Correcto	0.012 s	2 KBi
#8	Correcto	0.01 s	7 KBi
#9	Correcto	0.009 s	2 KBi
#10	Correcto	0.011 s	2 KBi
#11	Correcto	0.009 s	67 KBi
#12	Correcto	0.009 s	2 KBi
#13	Correcto	0.012 s	2 KBi
#14	Correcto	0.011 s	2 KBi
#15	Correcto	0.01 s	2 KBi
#16	Correcto	0.012 s	3 KBi
#17	Correcto	0.01 s	2 KBi
#18	Correcto	0.008 s	2 KBi
#19	Correcto	0.013 s	2 KBi
#20	Correcto	0.008 s	3 KBi
#21	Correcto	0.01 s	2 KBi
#22	Correcto	0.009 s	2 KBi

Puntos totales: 100 / 100

Código

#include <iostream>
#include <vector>

using namespace std;

#define ll long long


int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	string s;
	cin>>s;
	vector<int>kmp(s.size());
	for(int i=1; i<s.size();i++){
		int j = kmp[i-1];
		while(j>0 && s[i] != s[j]){
			j = kmp[j-1];
		}
		if(s[i] == s[j]){
			j++;
		}
		kmp[i]=j;
	}
	cout<<kmp[s.size()-1]<<endl;
	return 0;
}