Отдельные разные анаграммы

Question

Предположим, что у меня есть определенное количество строк, скажем n, хранящихся в случайном порядке в массиве. Несколько, скажем, m1, являются аналогами string1 и m2 являются аналогами string2 и так далее. Что было бы эффективным алгоритмом для выделения строк, которые являются анаграммами определенной строки и определения количества строк для каждого набора?

Answer 1

Интересный вопрос. То, что мы знаем об анаграмме, действительно сводится к двум вещам.

• они имеют одинаковую длину.
• они составлены из тех же символов.

определение первого условия легко, второе, не так много. сначала сортируя массив строк по длине, вы ограничиваете количество строк, которые вы должны выполнить во втором тесте.

2-й тест, по-видимому, требует, чтобы вы не только проверяли, что string1.contains (string2 [n]), но и вы также определяете, что они происходят одинаковое количество раз в каждой строке. Мне бы, вероятно, понадобилась копия массива строк, но я бы сделал его массивом char [], потому что строки неизменяемы. Затем я мог сортировать каждую строку в копии по ее символам компонента. Теперь анаграммы будут сопоставляться с string1 == string2.

Answer 2

#include<stdio.h> 
#include<string.h> 
int main() 
{ 
    char a[100],b[100],c[100],d[100]; 
    char temp; 
    int i,j; 
    printf("Enter the first string\n"); 
     gets(a); 
     printf("Enter the second string\n"); 
     gets(b); 
    strcpy(d,a); 
    strcpy(c,b); 
    for(i=0;i<strlen(a);i++) 
    { 
    if(a[i]==' ') 
    { 
    temp=a[i]; 
    a[i]=a[i+1]; 
     a[i+1]=temp; 
    } 
    } 
    a[strlen(a)]='\0'; 
    for(j=0;j<strlen(b);j++) 
    { 
    if(b[j]==' ') 
    { 
     temp=b[j]; 
     b[j]=b[j+1]; 
     b[j+1]=temp; 
    } 
} 
    b[strlen(b)]='\0'; 
if(strlen(a)==strlen(b)) 
    for(i=0;i<strlen(a);) 
    { 
     for(j=i;j<strlen(b);j++) 
     { 
     if(a[i]==b[j]) 
     { 
      temp=b[i]; 
     b[i]=a[i]; 
     b[j]=temp; 
      i++; 
      break; 
     } 
     } 
     } 
if(strcmp(a,b)==0) 
     printf("%s and %s are anagrams\n",d,c); 
     else 
     printf("%s and %s are not anagrams\n",d,c); 
     return(0); 
    }