Advertisement
Guest User

How many anagrams

a guest
Feb 14th, 2012
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.42 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. #define MAX_WORD_SIZE (50)
  6.  
  7. typedef struct {
  8.     char* w1;
  9.     char* w2;
  10. } anagram_t;
  11.  
  12. int anagram(char* word1, char* word2)
  13. {
  14.     size_t i;
  15.     char* w;
  16.  
  17.     if (strlen(word1) != strlen(word2))
  18.         return 0;
  19.  
  20.     if (strcmp(word1, word2) == 0)
  21.         return 0;
  22.    
  23.     for (i = 0; i < strlen(word1); ++i) {
  24.         w = strchr(word2, word1[i]);
  25.         if (w == NULL)
  26.             return 0;
  27.         *w = '-';
  28.     }
  29.  
  30.     return 1;
  31. }
  32.  
  33. int cmp(anagram_t* a, char* w1, char* w2)
  34. {
  35.     if (strcmp(a->w1, w1) == 0 &&
  36.         strcmp(a->w2, w2) == 0)
  37.         return 1;
  38.  
  39.     if (strcmp(a->w1, w2) == 0 &&
  40.         strcmp(a->w2, w1) == 0)
  41.         return 1;
  42.  
  43.     return 0;
  44. }
  45.  
  46. int main(int argc, char** argv)
  47. {
  48.     char** words;
  49.     char buff[MAX_WORD_SIZE];
  50.     size_t p, w, mw, count, ma;
  51.     int t;
  52.     anagram_t** a;
  53.     int c;
  54.     FILE* fp;
  55.  
  56.     if (argc != 2)
  57.         return 1;
  58.  
  59.     fp = fopen(argv[1], "r");
  60.     if (fp == NULL) {
  61.         printf("File not found.\n");
  62.         return 1;
  63.     }
  64.  
  65.     words = malloc(100 * sizeof(char*));
  66.     if (words == NULL)
  67.         return 1;
  68.  
  69.     w = 0;
  70.     mw = 100;
  71.     p = 0;
  72.     while ((c = fgetc(fp)) != EOF) {
  73.         if (c >= 'A' && c <= 'Z')
  74.             c += 32;
  75.         if (c < 'a' || c > 'z') {
  76.             if (p <= 1) {
  77.                 p = 0;
  78.                 continue;
  79.             }
  80.             if (w == mw) {
  81.                 mw += 100;
  82.                 words = realloc(words, mw * sizeof(char*));
  83.                 if (words == NULL)
  84.                     return 1;
  85.             }
  86.             words[w] = malloc(p + 1);
  87.             if (words[w] == NULL)
  88.                 return 1;
  89.             memcpy(words[w], buff, p);
  90.             words[w][p] = '\0';
  91.             w += 1;
  92.             p = 0;
  93.         } else {
  94.             buff[p++] = c;
  95.         }
  96.     }
  97.  
  98.     fclose(fp);
  99.     count = 0;
  100.     ma = 50;
  101.     a = malloc(ma * sizeof(anagram_t*));
  102.     if (a == NULL)
  103.         return 1;
  104.     for (p = 0; p < w - 1; ++p) {
  105.         for (mw = p + 1; mw < w; ++mw) {
  106.             memcpy(buff, words[mw], strlen(words[mw]) + 1);
  107.             if (anagram(words[p], buff)) {
  108.                 for (t = 0; t < count; ++t) {
  109.                     if (cmp(a[t], words[p], words[mw])) {
  110.                         t = -1;
  111.                         break;
  112.                     }
  113.                 }
  114.                 if (t > -1) {
  115.                     if (count == ma) {
  116.                         ma += 50;
  117.                         a = realloc(a, ma *
  118.                             sizeof(anagram_t*));
  119.                         if (a == NULL)
  120.                             return 1;
  121.                     }
  122.                     a[count] = malloc(sizeof(anagram_t));
  123.                     a[count]->w1 = words[p];
  124.                     a[count]->w2 = words[mw];
  125.                     count += 1;
  126.                 }
  127.             }
  128.         }
  129.     }
  130.  
  131.     printf("Number of anagrams: %lu\n", count);
  132.    
  133.     for (ma = 0; ma < count; ++ma)
  134.         printf("%s, %s\n", a[ma]->w1, a[ma]->w2);
  135.         free(a[ma]);
  136.     free(a);
  137.  
  138.     for (ma = 0; ma < w; ++ma)
  139.         free(words[ma]);
  140.     free(words);
  141.     return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement