Dadas dos strings s1 y s2, compruebe si s2 es una rotación de s1.
Ejemplos:
Input : ABACD, CDABA Output : True Input : GEEKS, EKSGE Output : True
Hemos discutido un enfoque en una publicación anterior que maneja la coincidencia de substrings como un patrón. En esta publicación, utilizaremos la construcción lps (prefijo propio más largo que también es sufijo) del algoritmo KMP , que ayudará a encontrar la coincidencia más larga del prefijo de la string b y el sufijo de la string a. Por lo cual conoceremos el punto de giro , a partir de este punto emparejar los personajes. Si todos los caracteres coinciden, entonces es una rotación, de lo contrario no.
A continuación se muestra la implementación básica del enfoque anterior.
Python3
# Python program to check if
# two strings are rotations
# of each other
def isRotation(a: str, b: str) -> bool:
n = len(a)
m = len(b)
if (n != m):
return False
# create lps[] that
# will hold the longest
# prefix suffix values
# for pattern
lps = [0 for _ in range(n)]
# length of the previous
# longest prefix suffix
length = 0
i = 1
# lps[0] is always 0
lps[0] = 0
# the loop calculates
# lps[i] for i = 1 to n-1
while (i < n):
if (a[i] == b[length]):
length += 1
lps[i] = length
i += 1
else:
if (length == 0):
lps[i] = 0
i += 1
else:
length = lps[length - 1]
i = 0
# Match from that rotating
# point
for k in range(lps[n - 1], m):
if (b[k] != a[i]):
return False
i += 1
return True
# Driver code
if __name__ == "__main__":
s1 = "ABACD"
s2 = "CDABA"
print("1" if isRotation(s1, s2) else "0")
# This code is contributed by sanjeev2552
Producción:
1
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Consulte el artículo completo sobre Comprobar si las strings son rotaciones entre sí o no | Set 2 para más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA