Рубрики

Найти, может ли данная строка быть представлена из подстроки, повторяя подстроку «n» раз

Учитывая строку 'str', проверьте, может ли она быть построена, взяв ее подстроку и добавив несколько копий подстроки вместе.

Примеры:

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

Источник: Google Интервью Вопрос

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Там может быть много решений этой проблемы. Задача состоит в том, чтобы решить задачу за O (n) раз. Ниже приведен алгоритм O (n).

Пусть заданная строка будет 'str', а длина заданной строки будет 'n'.

1) Найти длину самого длинного правильного префикса 'str', который также является суффиксом. Пусть длина самого длинного правильного суффикса префикса будет «len». Это может быть вычислено за время O (n) с использованием этапа предварительной обработки алгоритма сопоставления строк KMP .

2) Если значение 'n-len' делит n (или 'n% (n-len)' равно 0), тогда вернуть true, иначе вернуть false.

В случае 'true' подстрока 'str [0..n-len-1]' является подстрокой, которая повторяется n% (n-len) раз.

Давайте возьмем несколько примеров.

Ввод: str = «ABCDABCD», n = 8 (количество символов в «str»)
Значение len равно 4 («ABCD» — самая длинная подстрока, которая является как префиксом, так и суффиксом)
Поскольку (n-len) делит n, ответ верен.

Ввод: str = «ABCDABC», n = 7 (количество символов в «str»)
Значение len равно 3 («ABC» — самая длинная подстрока, которая является как префиксом, так и суффиксом)
Поскольку (n-len) не делит n, ответ неверен.

Ввод: str = «ABCABCABCABCABC», n = 15 (количество символов в «str»)
Значение len равно 12 («ABCABCABCABC» — самая длинная подстрока, которая является как префиксом, так и суффиксом)
Поскольку (n-len) делит n, ответ верен.

Как это работает?
длина самого длинного правильного префикса-суффикса (или len) всегда составляет от 0 до n-1. Если len равно n-1, то все символы в строке одинаковы. Например, len — 3 для «AAAA». Если len равно n-2, а n четно, то два символа в строке повторяются n / 2 раза. Например, «ABABABAB», длина lps равна 6. Причина в том, что если первые n-2 символа совпадают с последними n-2 символами, начиная с первой пары, каждая пара символов идентична следующей паре. Следующая диаграмма демонстрирует то же самое для подстроки длины 4.

Ниже приведена реализация вышеуказанного алгоритма:

C ++

// Программа на C ++ для проверки, является ли строка 'n' раз
// повтор одной из его подстрок
#include<iostream>
#include<cstring>

using namespace std;

  
// Утилита для заполнения lps [] или вычисления префикса funcrion
// используется в алгоритме сопоставления строк KMP. обращаться
// https://www.geeksforgeeks.org/archives/11902 для подробностей

void computeLPSArray(char str[], int M, int lps[])

{

    int len = 0; // длина предыдущего длинного суффикса префикса

    int i;

  

    lps[0] = 0; // lps [0] всегда 0

    i = 1;

  

    // цикл вычисляет lps [i] для i = 1 до M-1

    while (i < M)

    {

       if (str[i] == str[len])

       {

           len++;

           lps[i] = len;

           i++;

       }

       else // (pat [i]! = pat [len])

       {

          if (len != 0)

          {

             // Это сложно. Рассмотрим пример AAACAAAA

             // и я = 7.

             len = lps[len-1];

  

             // Также обратите внимание, что здесь мы не увеличиваем i

          }

          else // if (len == 0)

          {

             lps[i] = 0;

             i++;

          }

       }

    }

}

  
// Возвращает true, если str является повторением одной из своих подстрок
// еще вернем false.

bool isRepeat(char str[])

{

    // Найти длину строки и создать массив для

    // сохраняем значения lps, используемые в KMP

    int n = strlen(str);

    int lps[n];

  

    // Предварительная обработка шаблона (вычисление массива lps [])

    computeLPSArray(str, n, lps);

  

    // Находим длину самого длинного суффикса, который также

    // префикс ул.

    int len = lps[n-1];

  

    // Если существует суффикс, который также является префиксом AND

    // Длина оставшейся подстроки делит итог

    // длина, тогда str [0..n-len-1] это подстрока, которая

    // повторяется n / (n-len) раз (читатели могут печатать подстроку

    // и значение n / (n-len) для большей ясности.

    return (len > 0 && n%(n-len) == 0)? true: false;

}

  
// Программа драйвера для проверки вышеуказанной функции

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;

}

Джава

// Java-программа для проверки, является ли строка 'n'
// время повторения одной из его подстрок

import java.io.*;

class GFG {

  
// Утилита для заполнения lps [] или вычисления
// префикс funcrion, используемый при сопоставлении строк KMP
// алгоритм. обращаться
// https://www.geeksforgeeks.org/archives/11902
// для деталей

static void computeLPSArray(String str, int M, 

                                     int lps[])

{   

    // длина предыдущего

    // длинный суффикс префикса

    int len = 0

      

    int i;

  

    lps[0] = 0; // lps [0] всегда 0

    i = 1;

  

    // цикл вычисляет lps [i]

    // для i = 1 до 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)

        {

            // Это сложно. Рассмотрим

            // пример AAACAAAA и i = 7.

            len = lps[len-1];

  

            // Также обратите внимание, что мы делаем

            // здесь не увеличивается

        }

        else // if (len == 0)

        {

            lps[i] = 0;

            i++;

        }

    }

    }

}

  
// Возвращает true, если str является повторением
// одна из его подстрок еще возвращает false.

static boolean isRepeat(String str)

{

    // Найти длину строки и создать

    // массив для хранения значений lps, используемых в KMP

    int n = str.length();

    int lps[] = new int[n];

  

    // Предварительная обработка шаблона (вычисление массива lps [])

    computeLPSArray(str, n, lps);

  

    // Находим длину самого длинного суффикса

    // который также является префиксом str.

    int len = lps[n-1];

  

    // Если существует суффикс, который также

    // префикс AND Длина оставшейся подстроки

    // делит общую длину, затем str [0..n-len-1]

    // подстрока, которая повторяет n / (n-len)

    // раз (Читатели могут распечатать подстроку и

    // значение n / (n-len) для большей ясности.

    return (len > 0 && n%(n-len) == 0)? true: false;

}

  
// Программа драйвера для проверки вышеуказанной функции

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");

}
}
}

  
// Этот код предоставлен Prerna Saini

питон

# Программа на Python, чтобы проверить, является ли строка 'n' раз
# повторение одной из его подстрок

  
# Утилита для заполнения lps [] или вычисления префикса funcrion
# используется в алгоритме сопоставления строк KMP. обращаться
# https://www.geeksforgeeks.org/archives/11902 для подробностей

def computeLPSArray(string, M, lps):

    length = 0        # длина предыдущего длинного суффикса префикса

    i = 1

  

    lps[0] = 0    # lps [0] всегда 0

  

    # цикл вычисляет lps [i] для i = 1 до M-1

    while i < M:

        if string[i] == string[length]:

            length += 1

            lps[i] = length

            i += 1

        else:

            if length != 0:            

                # Это сложно. Рассмотрим пример AAACAAAA

                # и я = 7.

                length = lps[length-1]

  

                # Также обратите внимание, что мы не увеличиваем i здесь

            else:

                lps[i] = 0

                i += 1

  
# Возвращает true, если строка является повторением одной из ее подстрок
# еще вернуть false.

def isRepeat(string):

    # Найти длину строки и создать массив для

    # хранить значения lps, используемые в KMP

    n = len(string)

    lps = [0] * n

  

    # Предварительная обработка шаблона (вычисление массива lps [])

    computeLPSArray(string, n, lps)

  

    # Найти длину самого длинного суффикса, который также

    # префикс ул.

    length = lps[n-1]

  

    # Если существует суффикс, который также является префиксом AND

    # Длина оставшейся подстроки делит всего

    # length, то str [0..n-len-1] - это подстрока, которая

    # повторяется n / (n-len) раз (читатели могут печатать подстроку

    # и значение n / (n-len) для большей ясности.

    if len > 0 and n%(n-length) == 0:

        return True

    else:

        False

  
# Драйверная программа

txt = ["ABCABC", "ABABAB", "ABCDABCD", "GEEKSFORGEEKS",

        "GEEKGEEK", "AAAACAAAAC", "ABCDABC"]

n = len(txt)

for i in xrange(n):

    if isRepeat(txt[i]):

        print "True"

    else:

        print "False"

  
# Этот код предоставлен BHAVYA JAIN

C #

// C # программа для проверки, является ли строка 'n'
// время повторения одной из его подстрок

using System;

  

class GFG {

      

    // Утилита для заполнения lps [] или

    // вычисляем префикс funcrion, используемый в KMP

    // алгоритм сопоставления строк. обращаться

    // https://www.geeksforgeeks.org/archives/11902

    // для деталей

    static void computeLPSArray(String str, int M, 

                                         int []lps)

    

          

        // длина предыдущего

        // длинный суффикс префикса

        int len = 0; 

          

        int i;

      

        lps[0] = 0; // lps [0] всегда 0

        i = 1;

      

        // цикл вычисляет lps [i]

        // для i = 1 до M-1

        while (i < M)

        {

            if (str[i] == str[len])

            {

                len++;

                lps[i] = len;

                i++;

            }

            else // (pat [i]! = pat [len])

            {

                if (len != 0)

                {

                      

                    // Это сложно. Рассмотрим

                    // пример AAACAAAA и i = 7.

                    len = lps[len-1];

          

                    // Также обратите внимание, что мы делаем

                    // здесь не увеличивается

                }

                else // if (len == 0)

                {

                    lps[i] = 0;

                    i++;

                }

            }

        }

    }

      

    // Возвращает true, если str является повторением

    // одна из его подстрок еще возвращает false.

    static bool isRepeat(String str)

    {

          

        // Найти длину строки и создать

        // массив для хранения используемых значений lps

        // в КМП

        int n = str.Length;

        int[] lps = new int[n];

      

        // Предварительная обработка шаблона (вычисление

        // массив lps [])

        computeLPSArray(str, n, lps);

      

        // Находим длину самого длинного суффикса

        // который также является префиксом str.

        int len = lps[n-1];

  

        // Если существует суффикс, который также

        // префикс AND Длина оставшегося

        // подстрока делит общую длину, затем

        // str [0..n-len-1] это подстрока, которая

        // повторяется n / (n-len) раз (Читатели могут

        // выводим подстроку и значение n / (n-len)

        // для большей ясности.

        return (len > 0 && n % (n - len) == 0)

                               ? true : false;

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    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");

        }

    }

}

  
// Этот код предоставлен Sam007.

Выход:

True
True
True
False
True
True
False 

Сложность времени: временная сложность вышеупомянутого решения O (n), поскольку он использует алгоритм предварительной обработки KMP, который является линейным алгоритмом времени.

Эта статья предоставлена Харшитом Агравалом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти, может ли данная строка быть представлена из подстроки, повторяя подстроку «n» раз

0.00 (0%) 0 votes