как найти повторяющуюся строку в массиве строк

Question

У меня есть массив строк, из которого я должен найти повторяющуюся строку и затем удалить эту дублирующую строку, как у меня есть строка

 char aa[50]="Amit Hanish Mahesh Amit"

Теперь Амит дублирован и должен удалить его из строки.

#include "string.h"
main()
{
  char x[100] = "Amit Hanish Mahesh Amit";
  char y[3][100];
  int i = 0, k = 0, j = 0, c = 0, end, t;
  int current = 1;
  while (x[i] != '\0') {
    if (x[i] != ' ') {
      y[k][j] = x[i];
      j++;
      i++;
    } else {
      // c = c + 1;
      i++;
      k++;
      j = 0;
    }
    y[k][j] = '\0';
  }

  for (end = 1; end <= 3; end++) {
    for (t = 0; t < end; t++) {
      if (strcmp(y[end], y[t]) == 0) break;
    }
    if (end == t) {
      strcpy(y[current],y[t]);
       current++;
    }
  }
  y[current] = 0;
  printf("%s",y);
}

Я написал для этого небольшую процедуру. Не похоже, что она работает. У кого-нибудь есть предложения, где я ошибаюсь?

Answer 1

Другие ответы, которые вы получили, работают нормально для строк с небольшим числом (в вашем примере кода только 4).Но если вы сравниваете большое число, это будет довольно медленно, так как вы делаете n ^ 2 сравнений.Я бы предложил сначала разбить строку на массив строк, а затем отсортировать массив с помощью qsort ().В отсортированном массиве все дубликаты гарантированно будут смежными.Это сокращает время с n ^ 2 до n log n - время, необходимое для сортировки.

Answer 2

Я бы разделил строковый массив с помощью strtok (см. Справочную страницу).

Так что у меня было бы что-то вроде этого

char x[100]="Amit Hanish Mahesh Amit";

/* Preparing the result string */
size_t sz_result = sizeof(char) * (strlen(x) + 1);
char* result = (char*) malloc( sz_result );
result[0] = '\0';

/* Parsing the string from one element to the other */
char* elm = strtok(x, " ");
while( (elm = strtok(NULL, " ")) != NULL )
{
  ...

У вас будет каждый элемент строки, чтобы проверить, являются ли они уникальными.

Тогда я бы использовал что-то вроде hashmap (вы можете использовать один из glib), или я бы поместил элемент read string в новую строку, только если его еще нет.

Вот пример для второго решения:

  ...
  /* Is the element already in the result string? */
  if ( strstr(result, elm) == NULL )
  {
    /* Then we should add it */
    snprintf( result, sz_result - 1, "%s %s", result, elm );
  }
}

В конце концов, если вы хотите изменить x, просто скопируйте результат в x:

strncpy( x, result, 99 );

Вот пример кода (не оптимизирован, не использует примитивы strn * и т. Д.)

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


int main()
{
  char x[100]="Amit Hanish Mahesh Amit";

  /* Preparing the result string */
  size_t sz_result = sizeof(char) * (strlen(x) + 1);
  char* result = (char*) malloc( sz_result );
  result[0] = '\0';

  /* Parsing the string from one element to the other */
  char* elm = strtok(x, " ");
  if (elm != NULL) strcpy(result, elm);
  while( (elm = strtok(NULL, " ")) != NULL )
  {
    /* Is the element already in the result string? */
    if ( strstr(result, elm) == NULL )
    {
      /* Then we should add it */
      strcat( result, " " );
      strcat( result, elm );
    }
  }

  strcpy( x, result );

  fprintf( stdout, "Result: %s\n", x );
}

Answer 3

Чтобы удалить дубликаты из массива без сохранения порядка элементов:

1. сортировка массива
2. копирование уникальных элементов в начало массива
3. удалениехвост с дублирующими элементами

int remove_duplicates(StringArray array) {
  if (! (array and array->items)) return 0; // empty array or NULL

  StringArray_sort(array); // sort

  // unique_copy()
  String result = array->items, last = array->items + array->size;
  for (String first = array->items; first != last; ++result) {
    String_copy(result, first); // copy first to result
    for (String prev = first; ++first != last and String_cmp(prev, first) == 0;)
      { /* skip adjacent equal items */ }
  }
  // shrink
  return StringArray_remove(array, result, last);
}

Пример

int main() {
  char text[] = "Mahesh Amit  Hanish Amit";
  StringArray array = split(text, sizeof(text));
  StringArray_dump(array, "<"); // print array before removing duplicates
  if (remove_duplicates(array) < 0)
    perror("error remove_duplicates(), OS error if any");
  StringArray_dump(array, ">"); // print it after
  StringArray_destroy(array);
  return 0;
}

Где split():

StringArray split(const char* text, size_t size) {
  if (! (text and text[size-1] == '\0')) return NULL;

  StringArray array = StringArray_create();
  if (! array) return NULL;

  size_t n = -1;
  for (const char* p = text; p != text+size; p += n+1) {
    n = strcspn(p, " \t\n"); // find index of the next whitespace
    if (n == 0) continue; // skip consecutive whitespace

    // append characters in range [p, p+n)
    // as a string to the array
    const String string = String_create(p, n);
    if (StringArray_append(array, string) < 0) {
      String_destroy(string);
      StringArray_destroy(array);
      return NULL;
    }
    String_destroy(string);
   }  
  return array;
}

Выход

Mahesh<Amit<Hanish<Amit<
Amit>Hanish>Mahesh>

Полный исходный код

Answer 4

/* 
 * C Program to Find the Frequency of  Every Word in a 
 * given String
 */
#include <stdio.h>
#include <string.h>

void main()
{
    int count = 0, c = 0, i, j = 0, k, space = 0;
    char str[100], p[50][100], str1[20], ptr1[50][100];
    printf("Enter the string\n");
    scanf(" %[^\n]s", str);
    printf("string length is %d\n", strlen(str));
    for (i = 0;i<strlen(str);i++)
    {
        if ((str[i] == ' ')||(str[i] == ', ')||(str[i] == '.'))
        {
            space++;
        }
    }
    for (i = 0, j = 0, k = 0;j < strlen(str);j++)
    {
        if ((str[j] == ' ')||(str[j] == 44)||(str[j] == 46))  
        {    
            p[i][k] = '\0';
            i++;
            k = 0;
        }        
        else
             p[i][k++] = str[j];
    }
    k = 0;
    for (i = 0;i <= space;i++)
    {
        for (j = 0;j <= space;j++)
        {
            if (i == j)
            {
                strcpy(ptr1[k], p[i]);
                k++;
                count++;
                break;
            }
            else
            {
                if (strcmp(ptr1[j], p[i]) != 0)
                    continue;
                else
                    break;
            }
        }
    }
    for (i = 0;i < count;i++) 
    {
        for (j = 0;j <= space;j++)
        {
            if (strcmp(ptr1[i], p[j]) == 0)
                c++;
        }
        printf("%s -> %d times\n", ptr1[i], c);
        c = 0;
    }
}

Answer 5

Всегда забавно пытаться решать такие простые задачи в Си как упражнение. Вот мой дубль.

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

char* strstrn(const char *haystack, const char *needle, size_t needle_len)
{
    while((haystack = strchr(haystack, *needle)))
    {
        if (strncmp(haystack, needle, needle_len) == 0)
            return (char *) haystack;
        haystack++;
    }
    return NULL;
 }

char* find_duplicate(const char* str, size_t len, size_t dup_len)
{
    for(size_t i = 0; i < (len - dup_len); i++)
    {
        char* r = strstrn(str + i + 1, str + i, dup_len);
        if(r) return r;
    }
    return NULL;
}

int main(int argc, char** argv)
{
    if(argc < 3)
    {
        fprintf(stderr, "Usage: %s haystack dup_size\n", argv[0]);
        return 1;
    }
    char* haystack = argv[1];
    size_t len = atoi(argv[2]);
    char* r;
    while((r = find_duplicate(haystack, strlen(haystack), len)))
    {
        strcpy(r, r + len);
    }
    puts(haystack);
    return 0;
}

Answer 6

Я почти уверен, что следующая строка не предназначена (назначение, а не сравнение)

 if (end = t) {

Посмотрите, что произойдет, если вы наберете == и вернетесь, если у вас все еще естьпроблемы.

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