Метод пересечения строк

196

14 апреля 2019, 07:10

Более развернуто вопрос звучит так: Написать метод пересечения строк, результат должен содержать только те символы которые есть и в первой строке и во второй.Символы могут дублироваться т. е. если заданы строки "aabbccd"и "ddccaab", то третья строка должна содержать "aabccd"(на самом деле в данной задаче порядок вывода символов не важен). А так же под все это выделить память.

С памятью разобрался, но как делать все остальное понять не могу Вот код:

#include <iostream>
#include <string.h>
#include <time.h>
using namespace std;
class myString
{
private:
    int str_len, str_mem, step;
    char *str;
public:
        myString();
        ~myString();
        myString(int str_len);
        myString(const char *src);
        void mergeStrings();
        void showThat();
        void unique(string);
        string s1, s2, Ts,res;
};
myString::myString()
{
    step = 16;
    str_len = 0;
    str_mem = 32;
    str = new char[str_mem];
    str[0]='\0';
}
myString::myString(int str_len):str_len(0),str_mem(16), step(16), str(new char [16]){}
myString::myString(const char *src)
{
    str_len = strlen(src);
    step = 16;
    str_mem = step*((str_len+step)/step);
    str = new char[str_mem];
    strcpy(str, src);
}
myString::~myString()
{
    delete [] str;
}
void myString::showThat()
    {
        for(uint32_t i=0; i<str_len; i++)
            cout<<str[i];
        cout<<endl;
    }
/* Возможно это является ответом, но я совсем запутался во всем этом
void myString::unique(string smb)
{
    if(res.find(smb,0) == string::npos)
        if(smb != " ")
            res += smb;
}

void myString::mergeStrings()
{
    for(size_t i = 0; i < s1.size(); ++i)
        for(size_t j = 0; j < s2.size(); ++j)
            if(s1.at(i) == s2.at(j))
            {
                Ts = s1.at(i);
                unique(Ts);
            }
}
*/
int main()
{
    myString str1 = "Testing is my own passion", str2 = "I want to be a famous IT spec";
    str1.showThat();
    str2.showThat();
    //str1.mergeStrings(str2);
    str1.showThat();
    str2.showThat();
    return 0;
}

Answer 1

Так как, согласно условию, порядок символов в результате не важен, то

void myString::unique(myString smb)
{
  char *new_str = new char[str_mem];
  std::sort(str, str + str_len);
  std::sort(smb.str, smb.str + smb.str_len);
  char *new_str_end = 
    std::set_intersection(str, str + str_len, smb.str, smb.str + smb.str_len, new_str);
  *new_str_end = '\0';
  str_len = new_str_end - new_str;
  std::swap(str, new_str);
  delete[] new_str;
}
...
int main()
{
  myString str1 = "Testing is my own passion", str2 = "I want to be a famous IT spec";
  str1.showThat();
  str2.showThat();
  str1.unique(str2);
  str1.showThat();
  str2.showThat();
}

Однако для работоспособности такого кода вам сначала нужно привести ваш класс в соответствие с Правилом Трех.

Answer 2

Для больших строк сложность будет очень большой порядка O(m*n). Но если задача у вас всего-лишь научится писать циклы , то можете просто использовать их. (Вы уже почти написали.)

В жизни уже может быть потребоваться ускорение программы. Мне нравится хеширование. Создаёте массив размера 256 из типа bool или char. Он будет означать, что символ с кодом i присутствует в строке. Наибольшую строку - хешируете. И с маленькой строкой будете записывать только те символы, у которых хеш - положительный. Сложность выполнения будет линейным O(max(m,n)). В реальности принимают только быстрые программы, так-что дерзайте.

Алгоритм:

// g++ -Wall -Wextra -Wpedantic -Os hash.cpp
# include <string.h>
# include <string>
# include <stdint.h>
# include <iostream>
int main()  {
  uint8_t hash[256] ;
  memset(hash,0,256); // инициализация хеша с полным отрицанием всего
  std::string strbig = "Biggest string" ;
  std::cout<<"strbig = \""<<strbig<<"\""<<std::endl;
  for(size_t i=strbig.size();i>0;) {
    -- i;
    hash[(unsigned char)strbig[i]] = 1 ; }
  std::string strsmall = "SmlStr" ;
  std::cout<<"strsmall = \""<<strsmall<<"\""<<std::endl;
  std::string strresult ;
  for(size_t i=strsmall.size();i>0;) {
    -- i;
    char ci = strsmall[i] ;
    if(hash[(unsigned char)ci]) strresult += ci; }
  std::cout<<"strresult = \""<<strresult<<"\""<<std::endl;  }