БлогNot. Си: Вывести только те символы, которые встречаются в каждой из строк s1, s2

Си: Вывести только те символы, которые встречаются в каждой из строк s1, s2

Учебная задачка по Си (работа с указателями), кидаю сюда, чтобы не потерялась. Условие такое:

Вывести только те символы, которые встречаются в каждой из строк s1, s2. Задачу реализовать через написание собственной подпрограммы-функции, которой передаются параметрами указатели на строки s1 и s2. Функция возвращает указатель на новую строку, память под которую выделяется динамически.

Как будто, задача навскидку не сводится к применению стандартных методов, которые есть в классическом Си для подобных целей, например:

  • unsigned strspn (const char *s1, const char *s2) - возвращает индекс первого символа в строке s1, не совпадающего ни с одним из символов строки s2;
  • unsigned strсspn (const char *s1, const char *s2) - возвращает длину начальной подстроки в строке s1, не содержащей ни одного символа из строки s2.

Первое пришедшее в голову решение можно сделать вот такое, обычным двойным циклом:

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

int min (int a,int b) { return (a<b?a:b); }

char *f(char *s1, char *s2) {
 char *s=NULL;
 s=(char *)calloc(min(strlen(s1),strlen(s2)),sizeof(char));
 char *r=s;
 if (s) {
  while (*s1) {
   char *t=s2;
   while (*t) {
    if (*s1==*t) *s++=*t;
    t++;
   }
   s1++;
  }
  *s='\0';
 }
 return r;
}

void main () {
 char *s1="1asdf0", *s2="12as3400";
 puts (f(s1,s2)); getchar();
}

Однако, здесь дублирующиеся символы в самих s1 и s2 также будут напечатаны повторно, то есть, для теста на скриншоте получится строка 1as00

Если добавить в условие исключение повторяющихся символов из строки результата (для которого проще всего либо делать "вручную" ещё один проход по строке результата для исключения лишних символов, либо отсекать их стандартной функцией strchr, также делающей лишний проход), получим следующее решение (только изменённая функция):

char *f(char *s1, char *s2) {
 char *s=NULL;
 s=(char *)calloc(min(strlen(s1),strlen(s2)),sizeof(char));
 char *r=s;
 if (s) {
  while (*s1) {
   char *t=s2;
   while (*t) {
    if ((*s1==*t) && (strchr(r,*s1)==NULL))
     {
      *s++=*t; printf ("%c\n",*s1);
     }
    t++;
   }
   s1++;
  }
  *s='\0';
 }
 return r;
}

Теперь функция f(...) для теста

char *s1="001asdf0000", *s2="012as340";

выдаст, как положено, строку 01as

Подумайте, можно ли в принципе запрограммировать эту задачу менее, чем тройным циклом?


теги: textprocessing алгоритм c++

09.02.2011, 14:25; рейтинг: 9234