C ++ Comparison Text

Question

I was asked the following question:

If there are two line inputs, which method can be used to print letters that have line inputs. For example, if the user input:

works

soaked

output:

OK

What is the best algorithm to solve the problem?

Answer 1

string a = "working";
string b = "soaked";
set<char> setA(a.begin(), a.end());
set<char> setB(b.begin(), b.end());

vector<char> common;
set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(),
                 back_inserter(common));

copy(common.begin(), common.end(), ostream_iterator<char>(cout));

In fact, if further processing is not required at the intersection, you can send it directly to cout:

set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(),
                 ostream_iterator<char>(cout));

Answer 2

Your description is not unique, but, as I read it, you want to know which letters match the position.

#include <string>
#include <iostream>
#include <algorithm>

int main() {
  std::string const a = "working";
  std::string const b = "soaked";

  for (int i = 0; i < std::min(a.size(), b.size()); ++i) {
    if (a[i] == b[i]) {
      std::cout << a[i];
    }
  }
}

It produces:

ok

Answer 3

, .

26

bool array[26];

(letter-'a') (for upper letter-'A')

, cheking array[index]==true. , ;

:

 bool array[26];
  for(bool &arr:array )arr=false;
  char text1[]="working";
  char text2[]="soaked";
  char common[80]="";


  for(char x:text1){
    int m=x-'a'   ;
    if(m>=0 && m<26){
      array[m]   =true;
    }
  }
  int j=0;
  for(char x:text2){
    int m=x-'a'   ;
    if(m>=0 && m<26){
      if(array[m] ==true){
          common[j]=x;
          ++j;
           array[m]=false; //do not check again
      }

    }
  }
  common[j]='\0';
  printf("%s\n",common);

Answer 4

++, @Igor , . , - -, , , std::set_intersection:

input: string a, string c
output: string c with common letters

sort(a) // O(nlog(n))
sort(b) // O(mlog(m))
c = empty

i = 0
j = 0
// O(min(n,m))
while i < length(a) && j < length(b) do
  if a[i] == b[j]
    add(c, a[i])
    // increment indexes avoiding duplicates
    do i = i + 1 until a[i] != a[i-1] or i == length(a)
    do j = j + 1 until b[j] != b[j-1] or j == length(b)
  else if a[i] < b[j]
    i = binary_search from a[i+1] to a[end] for b[j]
  else
    j = binary_search from b[j+1] to b[end] for a[i]
  end 
end

// Total cost (nlog(n))
return c

Answer 5

, set_intersection , std::set. , , set_intersection, set_intersection .

, (, ) . . "" "", "" "".

Answer 6

:

std::set<char> common_characters(std::string const & a, std::string const & b) {
    std::set<char> common;

    std::string const & smaller = (a.size() < b.size()) ? a : b;
    std::string const & larger  = (a.size() < b.size()) ? b : a;

    std::set<char> chars(smaller.begin(), smaller.end());

    for (char i : larger) {
        auto found = chars.find(i);

        if (found != chars.end()) {
            common.insert(*found);
        }
    }

    return common;
}

, set_intersection() ( ), , .

Answer 7

, ( ), , , mergesort. C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int charcmp(char *p, char *q) { return *p - *q; }

int main() {
    char a[] = "working";
    char b[] = "soaked";

    int al = strlen(a);
    int bl = strlen(b);

    qsort(a, al, 1, charcmp);
    qsort(b, bl, 1, charcmp);

    int i = 0, j = 0;
    while (i < al && j < bl) {
        if      (a[i] == b[j]) { printf("%c", a[i]); i++; j++; }
        else if (a[i] < b[j])  {                     i++;      }
        else                   {                          j++; }
    }
    printf("\n");
}

Of course, if the lines are as short as in the example, there is no point in sorting, just scan one line and look at another. But this algorithm scales well with a very large string (it is linear and the search version is quadratic).