Dada una string ‘str’, verifique si se puede construir tomando una substring y agregando varias copias de la substring juntas.
Ejemplos:
Input: str = "abcabcabc" Output: true The given string is 3 times repetition of "abc" Input: str = "abadabad" Output: true The given string is 2 times repetition of "abad" Input: str = "aabaabaabaab" Output: true The given string is 4 times repetition of "aab" Input: str = "abcdabc" Output: false
Fuente: pregunta de la entrevista de Google
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Puede haber muchas soluciones a este problema. La parte desafiante es resolver el problema en tiempo O(n). A continuación se muestra un algoritmo O(n).
Deje que la string dada sea ‘str’ y la longitud de la string dada sea ‘n’.
- Encuentre la longitud del prefijo propio más largo de ‘str’, que también es un sufijo. Deje que la longitud del sufijo de prefijo propio más largo sea ‘len’. Esto se puede calcular en tiempo O(n) utilizando el paso de preprocesamiento del algoritmo de coincidencia de strings KMP .
- Si el valor de ‘n – len’ divide n (o ‘n % (n-len)’ es 0), entonces devuelve verdadero, de lo contrario devuelve falso.
En el caso de ‘true’, la substring ‘str[0..n-len-1]’ es la substring que se repite n/(n-len) veces.
Tomemos algunos ejemplos.
Entrada: str = “ABCDABCD”, n = 8 (Número de caracteres en ‘str’)
El valor de len es 4 (“ABCD” es la substring más larga que es tanto prefijo como sufijo)
Dado que (n-len) divide n, la respuesta es verdadera
Entrada: str = “ABCDABC”, n = 7 (Número de caracteres en ‘str’)
El valor de len es 3 (“ABC” es la substring más larga que es tanto prefijo como sufijo)
Dado que (n-len) no divide a n, la respuesta es falsa.
Entrada: str = «ABCABCABCABCABC», n = 15 (Número de caracteres en ‘str’)
El valor de len es 12 («ABCABCABCABC» es la substring más larga que es tanto prefijo como sufijo)
Dado que (n-len) divide n, la respuesta es verdadera
¿Como funciona esto?
la longitud del prefijo-sufijo propio más largo (o len) siempre está entre 0 y n-1. Si len es n-1, entonces todos los caracteres de la string son iguales. Por ejemplo, len es 3 para «AAAA». Si len es n-2 y n es par, entonces dos caracteres en la string se repiten n/2 veces. Por ejemplo, «ABABABAB», la longitud de lps es 6. La razón es que si los primeros n-2 caracteres son los mismos que los últimos n-2 caracteres, a partir del primer par, cada par de caracteres es idéntico al par siguiente. El siguiente diagrama demuestra lo mismo para la substring de longitud 4.
La siguiente es la implementación del algoritmo anterior:
C++
// A C++ program to check if a string is 'n' times
// repetition of one of its substrings
#include <bits/stdc++.h>
using namespace std;
// A utility function to fill lps[] or compute prefix
// function used in KMP string matching algorithm. Refer
// https://www.geeksforgeeks.org/archives/11902 for
// details
void computeLPSArray(char str[], int M, int lps[])
{
// length of the previous longest prefix suffix
int len = 0;
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M) {
if (str[i] == str[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
// This is tricky. Consider the example
// AAACAAAA and i = 7.
len = lps[len - 1];
// Also, note that we do not increment i
// here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Returns true if str is repetition of one of its
// substrings else return false.
bool isRepeat(char str[])
{
// Find length of string and create an array to
// store lps values used in KMP
int n = strlen(str);
int lps[n];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(str, n, lps);
// Find length of longest suffix which is also
// prefix of str.
int len = lps[n - 1];
// If there exist a suffix which is also prefix AND
// Length of the remaining substring divides total
// length, then str[0..n-len-1] is the substring that
// repeats n/(n-len) times (Readers can print substring
// and value of n/(n-len) for more clarity.
return (len > 0 && n % (n - len) == 0) ? true : false;
}
// Driver program to test above function
int main()
{
char txt[][100]
= { "ABCABC", "ABABAB", "ABCDABCD",
"GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC",
"ABCDABC" };
int n = sizeof(txt) / sizeof(txt[0]);
for (int i = 0; i < n; i++)
isRepeat(txt[i]) ? cout << "True\n"
: cout << "False\n";
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// A C++ program to check if a string is 'n' times
// repetition of one of its substrings
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
// A utility function to fill lps[] or compute prefix
// function used in KMP string matching algorithm. Refer
// https://www.geeksforgeeks.org/archives/11902 for
// details
void computeLPSArray(char str[], int M, int lps[])
{
// length of the previous longest prefix suffix
int len = 0;
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M) {
if (str[i] == str[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
// This is tricky. Consider the example
// AAACAAAA and i = 7.
len = lps[len - 1];
// Also, note that we do not increment i
// here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Returns true if str is repetition of one of its
// substrings else return false.
bool isRepeat(char str[])
{
// Find length of string and create an array to
// store lps values used in KMP
int n = strlen(str);
int lps[n];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(str, n, lps);
// Find length of longest suffix which is also
// prefix of str.
int len = lps[n - 1];
// If there exist a suffix which is also prefix AND
// Length of the remaining substring divides total
// length, then str[0..n-len-1] is the substring that
// repeats n/(n-len) times (Readers can print substring
// and value of n/(n-len) for more clarity.
return (len > 0 && n % (n - len) == 0) ? true : false;
}
// Driver program to test above function
int main()
{
char txt[][100]
= { "ABCABC", "ABABAB", "ABCDABCD",
"GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC",
"ABCDABC" };
int n = sizeof(txt) / sizeof(txt[0]);
for (int i = 0; i < n; i++)
isRepeat(txt[i]) ? printf("True\n")
: printf("False\n");
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to check if a string is 'n'
// times repetition of one of its substrings
import java.io.*;
class GFG {
// A utility function to fill lps[] or compute
// prefix function used in KMP string matching
// algorithm. Refer
// https://www.geeksforgeeks.org/archives/11902
// for details
static void computeLPSArray(String str, int M,
int lps[])
{
// length of the previous
// longest prefix suffix
int len = 0;
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i]
// for i = 1 to M-1
while (i < M) {
if (str.charAt(i) == str.charAt(len)) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
// This is tricky. Consider the
// example AAACAAAA and i = 7.
len = lps[len - 1];
// Also, note that we do
// not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Returns true if str is repetition of
// one of its substrings else return false.
static boolean isRepeat(String str)
{
// Find length of string and create
// an array to store lps values used in KMP
int n = str.length();
int lps[] = new int[n];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(str, n, lps);
// Find length of longest suffix
// which is also prefix of str.
int len = lps[n - 1];
// If there exist a suffix which is also
// prefix AND Length of the remaining substring
// divides total length, then str[0..n-len-1]
// is the substring that repeats n/(n-len)
// times (Readers can print substring and
// value of n/(n-len) for more clarity.
return (len > 0 && n % (n - len) == 0) ? true
: false;
}
// Driver program to test above function
public static void main(String[] args)
{
String txt[]
= { "ABCABC", "ABABAB", "ABCDABCD",
"GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC",
"ABCDABC" };
int n = txt.length;
for (int i = 0; i < n; i++) {
if (isRepeat(txt[i]) == true)
System.out.println("True");
else
System.out.println("False");
}
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# A Python program to check if a string is 'n' times # repetition of one of its substrings # A utility function to fill lps[] or compute prefix function # used in KMP string matching algorithm. Refer # https://www.geeksforgeeks.org/archives/11902 for details def computeLPSArray(string, M, lps): length = 0 # length of the previous longest prefix suffix i = 1 lps[0] = 0 # lps[0] is always 0 # the loop calculates lps[i] for i = 1 to M-1 while i < M: if string[i] == string[length]: length += 1 lps[i] = length i += 1 else: if length != 0: # This is tricky. Consider the example AAACAAAA # and i = 7. length = lps[length-1] # Also, note that we do not increment i here else: lps[i] = 0 i += 1 # Returns true if string is repetition of one of its substrings # else return false. def isRepeat(string): # Find length of string and create an array to # store lps values used in KMP n = len(string) lps = [0] * n # Preprocess the pattern (calculate lps[] array) computeLPSArray(string, n, lps) # Find length of longest suffix which is also # prefix of str. length = lps[n-1] # If there exist a suffix which is also prefix AND # Length of the remaining substring divides total # length, then str[0..n-len-1] is the substring that # repeats n/(n-len) times (Readers can print substring # and value of n/(n-len) for more clarity. if length > 0 and n%(n-length) == 0: return True else: False # Driver program txt = ["ABCABC", "ABABAB", "ABCDABCD", "GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC", "ABCDABC"] n = len(txt) for i in range(n): if isRepeat(txt[i]): print (True) else: print (False) # This code is contributed by BHAVYA JAIN
C#
// C# program to check if a string is 'n'
// times repetition of one of its substrings
using System;
class GFG {
// A utility function to fill lps[] or
// compute prefix function used in KMP
// string matching algorithm. Refer
// https://www.geeksforgeeks.org/archives/11902
// for details
static void computeLPSArray(String str, int M,
int []lps)
{
// length of the previous
// longest prefix suffix
int len = 0;
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i]
// for i = 1 to M-1
while (i < M)
{
if (str[i] == str[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the
// example AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do
// not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Returns true if str is repetition of
// one of its substrings else return false.
static bool isRepeat(String str)
{
// Find length of string and create
// an array to store lps values used
// in KMP
int n = str.Length;
int[] lps = new int[n];
// Preprocess the pattern (calculate
// lps[] array)
computeLPSArray(str, n, lps);
// Find length of longest suffix
// which is also prefix of str.
int len = lps[n-1];
// If there exist a suffix which is also
// prefix AND Length of the remaining
// substring divides total length, then
// str[0..n-len-1] is the substring that
// repeats n/(n-len) times (Readers can
// print substring and value of n/(n-len)
// for more clarity.
return (len > 0 && n % (n - len) == 0)
? true : false;
}
// Driver program to test above function
public static void Main()
{
String[] txt = {"ABCABC", "ABABAB",
"ABCDABCD", "GEEKSFORGEEKS",
"GEEKGEEK", "AAAACAAAAC",
"ABCDABC"};
int n = txt.Length;
for (int i = 0; i < n; i++)
{
if(isRepeat(txt[i]) == true)
Console.WriteLine("True");
else
Console.WriteLine("False");
}
}
}
// This code is contributed by Sam007.
Javascript
<script>
// Javascript program to check if a string is 'n'
// times repetition of one of its substrings
// A utility function to fill lps[] or
// compute prefix function used in KMP
// string matching algorithm. Refer
// https://www.geeksforgeeks.org/archives/11902
// for details
function computeLPSArray(str, M, lps)
{
// length of the previous
// longest prefix suffix
let len = 0;
let i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i]
// for i = 1 to M-1
while (i < M)
{
if (str[i] == str[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the
// example AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do
// not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Returns true if str is repetition of
// one of its substrings else return false.
function isRepeat(str)
{
// Find length of string and create
// an array to store lps values used
// in KMP
let n = str.length;
let lps = new Array(n);
lps.fill(0);
// Preprocess the pattern (calculate
// lps[] array)
computeLPSArray(str, n, lps);
// Find length of longest suffix
// which is also prefix of str.
let len = lps[n-1];
// If there exist a suffix which is also
// prefix AND Length of the remaining
// substring divides total length, then
// str[0..n-len-1] is the substring that
// repeats n/(n-len) times (Readers can
// print substring and value of n/(n-len)
// for more clarity.
return (len > 0 && n % (n - len) == 0)
? true : false;
}
let txt = ["ABCABC", "ABABAB",
"ABCDABCD", "GEEKSFORGEEKS",
"GEEKGEEK", "AAAACAAAAC",
"ABCDABC"];
let n = txt.length;
for (let i = 0; i < n; i++)
{
if(isRepeat(txt[i]) == true)
document.write("True" + "</br>");
else
document.write("False" + "</br>");
}
</script>
Producción
True True True False True True False
Complejidad de tiempo: la complejidad de tiempo de la solución anterior es O (n) ya que utiliza el algoritmo de preprocesamiento KMP, que es un algoritmo de tiempo lineal.
Este artículo es una contribución de Harshit Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Otro enfoque:
El problema anterior se puede resolver sin usar el algoritmo KMP y el espacio adicional.
Este enfoque utiliza dos punteros para comprobar el período mínimo de una string como primer paso. El período de una string es la longitud de la substring de prefijo que se puede repetir x (x = longitud/período) veces para construir la string dada.
por ejemplo: la string de entrada “ abcabcabcabc ” tiene un punto 3, lo que significa que podemos construir la string dada repitiendo los primeros 3 caracteres 4 (longitud/3=4) varias veces.
Acercarse:
- Inicialmente establezca el primer puntero – i en el índice 0 de la string dada y el segundo puntero – j en el 1er índice.
- verifique los caracteres en ambos índices. si ambos coinciden, tome el período como (ji) e incremente i y j.
- si no coincide, una vez más verifique si el carácter actual coincide con el primer carácter en el índice 0. si coincide, actualice el período como j(j-0=j) y establezca i en el siguiente carácter.
- Si ambos caracteres no coinciden, establezca i en 0 y actualice el período en -1.
- Al final, compruebe si el período calculado divide exactamente la longitud de la string. si no, actualice el período a -1. Esta verificación elimina la presencia de strings que terminan con un sufijo menor que el punto. por ejemplo, el período para la string «GEEKSFORGEEKS» se calcula como 8 pero la string de sufijo (GEEKS) tiene solo 5 caracteres y está incompleta.
Implementación:
C++
/*package whatever //do not write package name here */
#include <bits/stdc++.h>
using namespace std;
int findPeriod(string A)
{
int length = A.size();
// Initially consider there is no period for given
// String
int period = -1;
/*set two pointers one(i) at
index 0 and other(j) at index 1. increment j till
first character is obtained in the string*/
int i = 0;
for (int j = 1; j < length; j++) {
int currChar = A[j];
int comparator = A[i];
/*If current character matches with first
*character
*update period as the difference of j and i*/
if (currChar == comparator) {
period = (j - i);
i++;
}
/* if any mismatch occurs in between set i to
* zero also check if current character again
* matches
* with starting character. If matches, update
* period*/
else {
if (currChar == A[0]) {
i = 1;
period = j;
}
else {
i = 0;
period = -1;
}
}
}
/*check if the period is exactly dividing
* string if not reset the period to -1
* this eliminates partial substrings like
* e.g string -"GEEKSFORGEEKS" */
period = (length % period != 0) ? -1 : period;
return period;
}
int main()
{
vector<string> testStrings
= { "ABCABC", "ABABAB", "ABCDABCD",
"GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC",
"ABCDABC" };
int n = testStrings.size();
for (int i = 0; i < n; i++) {
if (findPeriod(testStrings[i]) == -1)
cout << "false\n";
else
cout << "True\n";
}
return 0;
}
// This code is contributed by rakeshsahni
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
public static int findPeriod(String A)
{
int length = A.length();
// Initially consider there is no period for given
// String
int period = -1;
/*set two pointers one(i) at
index 0 and other(j) at index 1. increment j till
first character is obtained in the string*/
int i = 0;
for (int j = 1; j < length; j++) {
int currChar = A.charAt(j);
int comparator = A.charAt(i);
/*If current character matches with first
*character
*update period as the difference of j and i*/
if (currChar == comparator) {
period = (j - i);
i++;
}
/* if any mismatch occurs in between set i to
* zero also check if current character again
* matches
* with starting character. If matches, update
* period*/
else {
if (currChar == A.charAt(0)) {
i = 1;
period = j;
}
else {
i = 0;
period = -1;
}
}
}
/*check if the period is exactly dividing
* string if not reset the period to -1
* this eliminates partial substrings like
* e.g string -"GEEKSFORGEEKS" */
period = (length % period != 0) ? -1 : period;
return period;
}
public static void main(String[] args)
{
String[] testStrings
= { "ABCABC", "ABABAB", "ABCDABCD",
"GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC",
"ABCDABC" };
int n = testStrings.length;
for (int i = 0; i < n; i++) {
if (findPeriod(testStrings[i]) == -1)
System.out.println("false");
else
System.out.println("True");
}
}
}
Python3
def findPeriod(A):
length = len(A)
# Initially consider there is no period for given
# String
period = -1
# set two pointers one(i) at
# index 0 and other(j) at index 1. increment j till
# first character is obtained in the string
i = 0
for j in range(1,length):
currChar = A[j]
comparator = A[i]
# If current character matches with first
# character
# update period as the difference of j and i
if (currChar == comparator):
period = (j - i)
i += 1
# if any mismatch occurs in between set i to
# zero also check if current character again
# matches
# with starting character. If matches, update
# period
else:
if (currChar == A[0]):
i = 1
period = j
else:
i = 0
period = -1
# check if the period is exactly dividing
# string if not reset the period to -1
# this eliminates partial substrings like
# e.g string -"GEEKSFORGEEKS"
period = -1 if (length % period != 0) else period
return period
testStrings = [ "ABCABC", "ABABAB", "ABCDABCD", "GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC", "ABCDABC" ]
n = len(testStrings)
for i in range(n):
if (findPeriod(testStrings[i]) == -1):
print("false")
else:
print("True")
# This code is contributed by shinjanpatra
C#
using System;
public class GFG{
public static int findPeriod(String A)
{
int length = A.Length;
// Initially consider there is no period for given
// String
int period = -1;
/*set two pointers one(i) at
index 0 and other(j) at index 1. increment j till
first character is obtained in the string*/
int i = 0;
for (int j = 1; j < length; j++) {
int currChar = A[j];
int comparator = A[i];
/*If current character matches with first
*character
*update period as the difference of j and i*/
if (currChar == comparator) {
period = (j - i);
i++;
}
/* if any mismatch occurs in between set i to
* zero also check if current character again
* matches
* with starting character. If matches, update
* period*/
else {
if (currChar == A[0]) {
i = 1;
period = j;
}
else {
i = 0;
period = -1;
}
}
}
/*check if the period is exactly dividing
* string if not reset the period to -1
* this eliminates partial substrings like
* e.g string -"GEEKSFORGEEKS" */
period = (length % period != 0) ? -1 : period;
return period;
}
static public void Main (){
// Code
String[] txt = {"ABCABC", "ABABAB",
"ABCDABCD", "GEEKSFORGEEKS",
"GEEKGEEK", "AAAACAAAAC",
"ABCDABC"};
int n = txt.Length;
for (int i = 0; i < n; i++)
{
if(findPeriod(txt[i]) == -1)
Console.WriteLine("False");
else
Console.WriteLine("True");
}
}
}
// This code is contributed by lokeshpotta20.
Javascript
<script>
function findPeriod(A)
{
let length = A.length;
// Initially consider there is no period for given
// String
let period = -1;
/*set two pointers one(i) at
index 0 and other(j) at index 1. increment j till
first character is obtained in the string*/
let i = 0;
for (let j = 1; j < length; j++) {
let currChar = A[j];
let comparator = A[i];
/*If current character matches with first
*character
*update period as the difference of j and i*/
if (currChar == comparator) {
period = (j - i);
i++;
}
/* if any mismatch occurs in between set i to
* zero also check if current character again
* matches
* with starting character. If matches, update
* period*/
else {
if (currChar == A[0]) {
i = 1;
period = j;
}
else {
i = 0;
period = -1;
}
}
}
/*check if the period is exactly dividing
* string if not reset the period to -1
* this eliminates partial substrings like
* e.g string -"GEEKSFORGEEKS" */
period = (length % period != 0) ? -1 : period;
return period;
}
// driver code
let testStrings = [ "ABCABC", "ABABAB", "ABCDABCD","GEEKSFORGEEKS", "GEEKGEEK", "AAAACAAAAC","ABCDABC" ];
let n = testStrings.length;
for (let i = 0; i < n; i++) {
if (findPeriod(testStrings[i]) == -1)
document.write("false","</br>");
else
document.write("True","</br>");
}
// This code is contributed by shinjanpatra
</script>
Producción
True True True false True True false
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