Se le dan dos strings str1 y str2 de la misma longitud. En un solo turno, puede rotar una string (str2) por 1 elemento de modo que su primer elemento se convierta en el último y el segundo se convierta en el primero como «abcd» cambiará a «bcda» después de la operación de un turno. Debe encontrar la operación de cambio mínima requerida para obtener el prefijo común de longitud máxima de str1 y str2.
Ejemplos:
Input : str1[] = "geeks",
str2 = "dgeek"
Output : Shift = 1,
Prefix = geek
Input : str1[] = "practicegeeks",
str2 = "coderpractice"
Output : Shift = 5
Prefix = practice
Enfoque ingenuo: cambie la segunda string una por una y realice un seguimiento de la longitud del prefijo más largo para cada turno, hay un total de n turnos y para cada turno, encontrar la longitud del prefijo común llevará O (n) tiempo. Por lo tanto, la complejidad de tiempo general para este enfoque es O (n ^ 2).
Mejor enfoque: si agregamos una segunda string al final de sí misma que es str2 = str2 + str2, entonces no hay necesidad de encontrar un prefijo para cada turno por separado. Ahora, después de agregar str2 a sí mismo, solo tenemos que encontrar el prefijo más largo de str1 presente en str2 y la posición inicial de ese prefijo en str2 nos dará la cantidad real de turnos requeridos. Para encontrar el prefijo más largo, podemos usar el algoritmo de búsqueda de patrones KMP.
Entonces, de esta manera, nuestra complejidad temporal se reducirá a O(n) solamente.
Implementación
C++
// CPP program to find longest common prefix
// after rotation of second string.
#include <bits/stdc++.h>
using namespace std;
// function for KMP search
void KMP(int m, int n, string str2, string str1)
{
int pos = 0, len = 0;
// preprocessing of longest proper prefix
int p[m + 1];
int k = 0;
p[1] = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 && str1[k] != str1[i - 1])
k = p[k];
if (str1[k] == str1[i - 1])
++k;
p[i] = k;
}
// find out the longest prefix and position
for (int j = 0, i = 0; i < m; i++) {
while (j > 0 && str1[j] != str2[i])
j = p[j];
if (str1[j] == str2[i])
j++;
// for new position with longer prefix in str2
// update pos and len
if (j > len) {
len = j;
pos = i - j + 1;
}
}
// print result
cout << "Shift = " << pos << endl;
cout << "Prefix = " << str1.substr(0, len);
}
// driver function
int main()
{
string str1 = "geeksforgeeks";
string str2 = "forgeeksgeeks";
int n = str1.size();
str2 = str2 + str2;
KMP(2 * n, n, str2, str1);
return 0;
}
Java
// Java program to find longest common prefix
// after rotation of second string.
class GFG {
// function for KMP search
static void KMP(int m, int n,
String str2, String str1)
{
int pos = 0, len = 0;
int []p = new int[m + 1];
int k = 0;
//p[1] = 0;
char []ch1 = str1.toCharArray();
char []ch2 = str2.toCharArray();
for (int i = 2; i <= n; i++)
{
while (k > 0 && ch1[k] != ch1[i - 1])
k = p[k];
if (ch1[k] == ch1[i - 1])
++k;
p[i] = k;
}
// find out the longest prefix and position
for (int j = 0, i = 0; i < m; i++)
{
while (j > 0 && j < n && ch1[j] != ch2[i])
j = p[j];
if (j < n && ch1[j] == ch2[i])
j++;
// for new position with longer prefix in str2
// update pos and len
if (j > len)
{
len = j;
pos = i - j + 1;
}
}
// print result
System.out.println("Shift = " + pos);
System.out.println("Prefix = " +
str1.substring(0,len));
}
// Driver code
public static void main(String[] args)
{
String str1 = "geeksforgeeks";
String str2 = "forgeeksgeeks";
int n = str1.length();
str2 = str2 + str2;
KMP(2 * n, n, str2, str1);
}
}
// This code is contributed by Ita_c.
Python3
# Python3 program to find longest common prefix
# after rotation of second string.
# function for KMP search
def KMP(m, n, str2, str1):
pos = 0
Len = 0
# preprocessing of longest proper prefix
p = [0 for i in range(m + 1)]
k = 0
for i in range(2, n + 1):
while (k > 0 and str1[k] != str1[i - 1]):
k = p[k]
if (str1[k] == str1[i - 1]):
k += 1
p[i] = k
# find out the longest prefix and position
j = 0
for i in range(m):
while (j > 0 and j < n and str1[j] != str2[i]):
j = p[j]
if (j < n and str1[j] == str2[i]):
j += 1
# for new position with longer prefix
# in str2 update pos and Len
if (j > Len):
Len = j
pos = i - j + 1
# print result
print("Shift = ", pos)
print("Prefix = ", str1[:Len])
# Driver Code
str1 = "geeksforgeeks"
str2 = "forgeeksgeeks"
n = len(str1)
str2 = str2 + str2
KMP(2 * n, n, str2, str1)
# This code is contributed by Mohit kumar 29
C#
// C# program to find longest common prefix
// after rotation of second string.
using System;
class GFG {
// function for KMP search
static void KMP(int m, int n,
String str2, String str1)
{
int pos = 0, len = 0;
int []p = new int[m + 1];
int k = 0;
//p[1] = 0;
char []ch1 = str1.ToCharArray();
char []ch2 = str2.ToCharArray();
for (int i = 2; i <= n; i++)
{
while (k > 0 && ch1[k] != ch1[i - 1])
k = p[k];
if (ch1[k] == ch1[i - 1])
++k;
p[i] = k;
}
// find out the longest prefix and position
for (int j = 0, i = 0; i < m; i++)
{
while (j > 0 && j < n && ch1[j] != ch2[i])
j = p[j];
if (j < n && ch1[j] == ch2[i])
j++;
// for new position with longer prefix in str2
// update pos and len
if (j > len)
{
len = j;
pos = i - j + 1;
}
}
// print result
Console.WriteLine("Shift = " + pos);
Console.WriteLine("Prefix = " +
str1.Substring(0,len));
}
// Driver code
public static void Main(String[] args)
{
String str1 = "geeksforgeeks";
String str2 = "forgeeksgeeks";
int n = str1.Length;
str2 = str2 + str2;
KMP(2 * n, n, str2, str1);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find longest common prefix
// after rotation of second string.
// function for KMP search
function KMP(m, n, str2, str1)
{
var pos = 0, len = 0;
// preprocessing of longest proper prefix
var p = Array(m+1).fill(0);
var k = 0;
p[1] = 0;
for (var i = 2; i <= n; i++) {
while (k > 0 && str1[k] != str1[i - 1])
k = p[k];
if (str1[k] == str1[i - 1])
++k;
p[i] = k;
}
// find out the longest prefix and position
for (var j = 0, i = 0; i < m; i++) {
while (j > 0 && str1[j] != str2[i])
j = p[j];
if (str1[j] == str2[i])
j++;
// for new position with longer prefix in str2
// update pos and len
if (j > len) {
len = j;
pos = i - j + 1;
}
}
// print result
document.write( "Shift = " + pos + "<br>");
document.write( "Prefix = " + str1.substr(0, len));
}
// driver function
var str1 = "geeksforgeeks";
var str2 = "forgeeksgeeks";
var n = str1.length;
str2 = str2 + str2;
KMP(2 * n, n, str2, str1);
</script>
Producción:
Shift = 8 Prefix = geeksforgeeks
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA