Рубрики

Программа для проверки, являются ли строки вращением друг друга или нет

Учитывая строку s1 и строку s2, напишите фрагмент, чтобы сказать, является ли s2 поворотом s1?
(например, если s1 = ABCD и s2 = CDAB, вернуть true, если s1 = ABCD и s2 = ACBD, вернуть false)


Алгоритм:
areRotations (str1, str2)

    1. Create a temp string and store concatenation of str1 to
       str1 in temp.
                          temp = str1.str1
    2. If str2 is a substring of temp then str1 and str2 are 
       rotations of each other.

    Example:                 
                     str1 = "ABACD"
                     str2 = "CDABA"

     temp = str1.str1 = "ABACDABACD"
     Since str2 is a substring of temp, str1 and str2 are 
     rotations of each other.

C ++

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

using namespace std;

  
/ * Функция проверяет, переданы ли строки (str1

   и str2) являются вращениями друг друга * /

bool areRotations(string str1, string str2)

{

   / * Проверьте, совпадают ли размеры двух строк * /

   if (str1.length() != str2.length())

        return false;

  

   string temp = str1 + str1; 

  return (temp.find(str2) != string::npos);

}

  
/ * Драйвер программы для проверки areRotations * /

int main()

{

   string str1 = "AACD", str2 = "ACDA";

   if (areRotations(str1, str2))

     printf("Strings are rotations of each other");

   else

      printf("Strings are not rotations of each other");

   return 0;

}

С

     
// C-программа для проверки, являются ли две данные строки вращениями
// друг с другом
# include <stdio.h>
# include <string.h>
# include <stdlib.h>

  
/ * Функция проверяет, были ли переданы строки (str1 и str2)

   это вращения друг друга * /

int areRotations(char *str1, char *str2)

{

  int size1   = strlen(str1);

  int size2   = strlen(str2);

  char *temp;

  void *ptr;

  

  / * Проверьте, совпадают ли размеры двух строк * /

  if (size1 != size2)

     return 0;

  

  / * Создать временную строку со значением str1.str1 * /

  temp   = (char *)malloc(sizeof(char)*(size1*2 + 1));

  temp[0] = '';

  strcat(temp, str1);

  strcat(temp, str1);

  

  / * Теперь проверьте, является ли str2 подстрокой temp * /

  ptr = strstr(temp, str2);

  

  free(temp); // Освобождаем динамически выделяемую память

  

  / * strstr возвращает NULL, если вторая строка НЕ является

    подстрока первой строки * /

  if (ptr != NULL)

    return 1;

  else

    return 0;

}

  
/ * Драйвер программы для проверки areRotations * /

int main()

{

    char *str1 = "AACD";

    char *str2 = "ACDA";

  

    if (areRotations(str1, str2))

       printf("Strings are rotations of each other");

    else

       printf("Strings are not rotations of each other");

  

    getchar();

    return 0;

}

Джава

    
// Java-программа для проверки, являются ли две данные строки вращением
// друг с другом

  

class StringRotation

{

    / * Функция проверяет, были ли переданы строки (str1 и str2)

       это вращения друг друга * /

    static boolean areRotations(String str1, String str2)

    {

        // Длина должна быть одинаковой, а str2 должен быть

        // подстрока str1, объединенная с str1.

        return (str1.length() == str2.length()) &&

               ((str1 + str1).indexOf(str2) != -1);

    }

      

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

    public static void main (String[] args)

    {

        String str1 = "AACD";

        String str2 = "ACDA";

  

        if (areRotations(str1, str2))

            System.out.println("Strings are rotations of each other");

        else

            System.out.printf("Strings are not rotations of each other");

    }

}
// Этот код предоставлен munjal

питон

     
# Программа Python для проверки, являются ли строки вращением
# друг друга или нет

  
# Функция проверяет, переданы ли строки (str1 и str2)
# являются вращениями друг друга

def areRotations(string1, string2):

    size1 = len(string1)

    size2 = len(string2)

    temp = ''

  

    # Проверьте, совпадают ли размеры двух строк

    if size1 != size2:

        return 0

  

    # Создать временную строку со значением str1.str1

    temp = string1 + string1

  

    # Теперь проверьте, является ли str2 подстрокой temp

    # string.count возвращает количество вхождений

    # вторая строка в temp

    if (temp.count(string2)> 0):

        return 1

    else:

        return 0

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

string1 = "AACD"

string2 = "ACDA"

  

if areRotations(string1, string2):

    print "Strings are rotations of each other"

else:

    print "Strings are not rotations of each other"

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

C #

// C # программа для проверки наличия двух заданных строк
// это вращения друг друга

using System;

  

class GFG {

      

    / * Функция проверяет, переданы ли строки

    (str1 и str2) - это повороты

    друг с другом */

    static bool areRotations(String str1,

                                 String str2)

    {

          

        // Там длины должны быть одинаковыми и

        // str2 должен быть подстрокой

        // str1 объединяется с str1.

        return (str1.Length == str2.Length )

             && ((str1 + str1).IndexOf(str2)

                                     != -1);

    }

      

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

    public static void Main ()

    {

        String str1 = "FGABCDE";

        String str2 = "ABCDEFG";

  

        if (areRotations(str1, str2))

            Console.Write("Strings are"

            + " rotation s of each other");

        else

            Console.Write("Strings are "

           + "not rotations of each other");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Php программа для проверки
// две заданные строки
// вращения друг друга

  
/ * Проверка функций, если они пройдены
строки (str1 и str2) являются
вращения друг друга * /

function areRotations($str1, $str2)

{
/ * Проверьте, если размеры двух

   строки одинаковые * /

if (strlen($str1) != strlen($str2))

{

        return false;

}

  

$temp = $str1 + $str1

if ($temp.count($str2)> 0)

{

        return true;

}
else
{

    return false;

}
}

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

$str1 = "AACD";

$str2 = "ACDA";

if (areRotations($str1, $str2))

{

    echo "Strings are rotations "

                  "of each other";

}
else
{

    echo "Strings are not "

         "rotations of each other" ;

}

  
// Этот код добавлен
// от Shivi_Aggarwal.
?>


Выход:

Strings are rotations of each other

Используемые библиотечные функции:
strstr:
strstr находит подстроку в строке.
Прототип: char * strstr (const char * s1, const char * s2);
См. Http://www.lix.polytechnique.fr/Labo/Leo.Liberti/public/computing/prog/c/C/MAN/strstr.htm для получения дополнительной информации.

strcat:
strncat объединяет две строки
Прототип: char * strcat (char * dest, const char * src);
См. Http://www.lix.polytechnique.fr/Labo/Leo.Liberti/public/computing/prog/c/C/MAN/strcat.htm для получения дополнительной информации.

Сложность времени: временная сложность этой проблемы зависит от реализации функции strstr.
Если реализация strstr выполняется с использованием сопоставления KMP, то сложность вышеуказанной программы равна (-) (n1 + n2), где n1 и n2 — длины строк. KMP matcher занимает (-) (n) время, чтобы найти подстроку в строке длины n, где длина подстроки предполагается меньше, чем строка.

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

Программа для проверки, являются ли строки вращением друг друга или нет

0.00 (0%) 0 votes