Рубрики

Генерация всех вращений данной строки

Задана строка S. Задача состоит в том, чтобы напечатать все возможные повернутые строки заданной строки.

Примеры:

Input : S = "geeks"
Output : geeks
         eeksg
         eksge
         ksgee
         sgeek

Input : S = "abc" 
Output : abc
         bca
         cab

Способ 1 (простой)
Идея состоит в том, чтобы запустить цикл от i = 0 до n — 1 (n = длина строки), т.е. для каждой точки вращения скопируйте вторую часть строки во временную строку, а затем скопируйте первую часть исходной строки. во временную строку.

Ниже приведена реализация этого подхода:

C ++

// Простая программа на C ++ для генерации всех вращений
// данной строки
#include<bits/stdc++.h>

using namespace std;

  
// Распечатать всю повернутую строку.

void printRotatedString(char str[])

{

    int len = strlen(str);

  

    // Генерируем все повороты по очереди и печатаем

    char temp[len];

    for (int i = 0; i < len; i++)

    {

        int j = i;  // Текущий индекс в стр

        int k = 0;  // Текущий индекс в темп

  

        // Копируем вторую часть из точки

        // вращения.

        while (str[j] != '\0')

        {

            temp[k] = str[j];

            k++;

            j++;

        }

  

        // Копируем первую часть из точки

        // вращения.

        j = 0;

        while (j < i)

        {

            temp[k] = str[j];

            j++;

            k++;

        }

  

        printf("%s\n", temp);

    }

}

  
// Управляемая программа

int main()

{

    char str[] = "geeks";

    printRotatedString(str);

    return 0;

}

Джава

// Простая Java-программа для генерации всех вращений
// данной строки

  

class Test

{

    // Распечатать всю повернутую строку.

    static void printRotatedString(String str)

    {

        int len = str.length();

       

        // Генерируем все повороты по очереди и печатаем

        StringBuffer sb; 

          

        for (int i = 0; i < len; i++)

        {

            sb = new StringBuffer();

              

            int j = i;  // Текущий индекс в стр

            int k = 0// Текущий индекс в темп

       

            // Копируем вторую часть из точки

            // вращения.

            for (int k2 = j; k2 < str.length(); k2++) {

                sb.insert(k, str.charAt(j));

                k++;

                j++;

            }

       

            // Копируем первую часть из точки

            // вращения.

            j = 0;

            while (j < i)

            {

                sb.insert(k, str.charAt(j));

                j++;

                k++;

            }

       

            System.out.println(sb);

        }

    }

      

    // Метод драйвера

    public static void main(String[] args) 

    {

        String  str = new String("geeks");

        printRotatedString(str);

    }

}

python3

# Простая программа на Python3 для генерации
# все повороты данной строки

  
# Распечатать все повернутые строки.

def printRotatedString(str): 

  

    lenn = len(str

  

    # Генерация всех вращений

    # один за другим и распечатать

    temp = [0] * (lenn)

    for i in range(lenn):     

        j = i # Текущий индекс в стр

        k = 0 # Текущий индекс в темп

  

        # Копирование второй части из

        # точка вращения.

        while (j < len(str)): 

          

            temp[k] = str[j] 

            k += 1

            j += 1

          

  

        # Копирование первой части из

        # точка вращения.

        j = 0

        while (j < i) :

          

            temp[k] = str[j] 

            j += 1

            k += 1

          

  

        print(*temp, sep = "") 

      
Код водителя

if __name__ == '__main__':

    str = "geeks"

    printRotatedString(str)

      
# Этот код добавлен
# от SHUBHAMSINGH10

C #

// Простая программа на C # для генерации
// все повороты данной строки

using System;

using System.Text;

  

class GFG

{
// Распечатать всю повернутую строку.

public static void printRotatedString(string str)

{

    int len = str.Length;

  

    // Генерируем все повороты один

    // по одному и печатать

    StringBuilder sb;

  

    for (int i = 0; i < len; i++)

    {

        sb = new StringBuilder();

  

        int j = i; // Текущий индекс в стр

        int k = 0; // Текущий индекс в темп

  

        // Копируем вторую часть из

        // точка вращения.

        for (int k2 = j; k2 < str.Length; k2++)

        {

            sb.Insert(k, str[j]);

            k++;

            j++;

        }

  

        // Копируем первую часть из

        // точка вращения.

        j = 0;

        while (j < i)

        {

            sb.Insert(k, str[j]);

            j++;

            k++;

        }

  

        Console.WriteLine(sb);

    }

}

  
// Код драйвера

public static void Main(string[] args)

{

    string str = "geeks";

    printRotatedString(str);

}
}

  
// Этот код добавлен
// от Shrikant13

PHP

<?php
// Простая PHP-программа для генерации
// все повороты данной строки

  
// Распечатать всю повернутую строку.

function printRotatedString($str)

{

    $len = strlen($str);

  

    // Генерируем все повороты один

    // по одному и печатать

    $temp = " ";

    for ($i = 0; $i < $len; $i++)

    {

        $j = $i; // Текущий индекс в стр

        $k = 0;  // Текущий индекс в темп

  

        // Копируем вторую часть из

        // точка вращения.

        while ($j < $len)

        {

            $temp[$k] = $str[$j];

            $k++;

            $j++;

        }

  

        // Копируем первую часть из

        // точка вращения.

        $j = 0;

        while ($j < $i)

        {

            $temp[$k] = $str[$j];

            $j++;

            $k++;

        }

  

        echo $temp . "\n";

    }

}

  
// Код драйвера

$str = "geeks";

printRotatedString($str);

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

geeks
eeksg
eksge
ksgee
sgeek

Метод 1 (хитрый и эффективный)

Идея основана на эффективном методе проверки, являются ли строки вращением друг друга или нет . Мы объединяем str с самим собой, т. Е. Делаем str.str где. является оператором конкатенации. Теперь мы пересекаем составную строку от 0 до n — 1 и печатаем все подстроки размера n.

Ниже приведена реализация этого подхода:

C ++

// Эффективная программа C ++ для печати всех
// повороты строки.
#include<bits/stdc++.h>

using namespace std;

  
// Распечатать всю повернутую строку.

void printRotatedString(char str[])

{

    int n = strlen(str);

  

    // Объединяем str с собой

    char temp[2*n + 1];

    strcpy(temp, str);

    strcat(temp, str);

  

    // Распечатать все подстроки размера n.

    // Обратите внимание, что размер temp равен 2n

    for (int i = 0; i < n; i++)

    {

        for (int j=0; j != n; j++)

            printf("%c",temp[i + j]);

        printf("\n");

    }

}

  
// Управляемая программа

int main()

{

    char str[] = "geeks";

    printRotatedString(str);

    return 0;

}

Джава

// Простая Java-программа для генерации всех вращений
// данной строки

  

class Test

{

    // Распечатать всю повернутую строку.

    static void printRotatedString(String str)

    {

        int n = str.length();

        

        StringBuffer sb = new StringBuffer(str);

        // Объединяем str с собой

        sb.append(str);

       

        // Распечатать все подстроки размера n.

        // Обратите внимание, что размер sb равен 2n

        for (int i = 0; i < n; i++)

        {

            for (int j=0; j != n; j++)

                System.out.print(sb.charAt(i + j));

            System.out.println();

        }

    }

      

    // Метод драйвера

    public static void main(String[] args) 

    {

        String  str = new String("geeks");

        printRotatedString(str);

    }

}

python3

# Эффективная программа на Python3 для печати
# все повороты строки.

  
# Распечатать всю повернутую строку.

def printRotatedString(string) :

      

    n = len(string)

  

    # Объединить ул с собой

    temp = string + string

  

    # Вывести все подстроки размером n.

    # Обратите внимание, что размер temp равен 2n

    for i in range(n) :

          

        for j in range(n) :

            print(temp[i + j], end = "")

              

        print() 

  
Код водителя

if __name__ == "__main__"

  

    string = "geeks"

    printRotatedString(string)

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

C #

// Простая программа на C # для генерации всех вращений
// данной строки

using System;

using System.Text;

  

class Test

{

      

    // Распечатать всю повернутую строку.

    static void printRotatedString(String str)

    {

        int n = str.Length;

      

        StringBuilder sb = new StringBuilder(str);

        // Объединяем str с собой

        sb.Append(str);

      

        // Распечатать все подстроки размера n.

        // Обратите внимание, что размер sb равен 2n

        for (int i = 0; i < n; i++)

        {

            for (int j=0; j != n; j++)

                Console.Write(sb[i + j]);

            Console.WriteLine();

        }

    }

      

    // Метод драйвера

    public static void Main(String[] args) 

    {

        String str = "geeks";

        printRotatedString(str);

    }

}

PHP

<?php
// Эффективная PHP-программа для печати всех
// повороты строки.

  
// Распечатать всю повернутую строку.

function printRotatedString($str)

{

    $n = strlen($str);

  

    // Объединяем str с собой

    $temp=$str.$str;

  

    // Распечатать все подстроки размера n.

    // Обратите внимание, что размер temp равен 2n

    for ($i = 0; $i < $n; $i++)

    {

        for ($j = 0; $j != $n; $j++)

            print($temp[$i + $j]);

        print("\n");

    }

}

  

    // Код драйвера

    $str = "geeks";

    printRotatedString($str);

      
// Этот код предоставлен mits
?>


Выход:

geeks
eeksg
eksge
ksgee
sgeek

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Генерация всех вращений данной строки

0.00 (0%) 0 votes