anagram program

[meriororen]

Hi there people,

I need a little help here with a program I made, its about finding how many pairs of anagram there are in a given input (can be from keyboard, or a text data). The number of words given are not known before EOF.

for example data.txt :

atm
mat
rat
art
spit
pits
run

will give me 4 (assuming that "run" is a pair of anagram to itself)
words are all in lowercase and no space,

here is my program :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 33


int areAnags(char *str1, char *str2){
	int i,temp;
	int count1[256] = {0}; 
	int count2[256] = {0};
	
	if(strlen(str1) != strlen(str2)) return 0;	

	for(i=0;i<strlen(str1);i++){
		temp = (int)str1[i];
		count1[temp]++;
	}
	for(i=0;i<strlen(str2);i++){
		temp = (int)str2[i];
		count2[temp]++;
	}

	for(i=97;i<=122;i++){
		if(count1[i] != count2[i]) return 0;	
	}
	
	return 1;
}


int main(void){
	char input[MAX];
	int count = 0,i;
	char **anagram = NULL;
	
	anagram = malloc(sizeof(char *));
	anagram[0] = malloc(MAX * sizeof(char));
	if(anagram == NULL){
		printf("Insufficient memory available.\n");		
		return EXIT_FAILURE;
	}

	while(scanf("%s", input) != EOF){	
		anagram[0] = strdup(input);
		for(i=0;i<sizeof(anagram);i++){
			if(areAnags(anagram[i],input) == 0){
				anagram = realloc(anagram, (count+1) * sizeof(char *));
				anagram[count] = malloc(MAX * sizeof(char));

				if(anagram == NULL || anagram[count] == NULL){
						printf("Insufficient memory available.\n");		
						return EXIT_FAILURE;		
				}
					
				anagram[count] = strdup(input);
				count++;
			}
		}
	}

	for(i=0;i<count;i++)	
		printf("%d\n", sizeof(anagram));
	

	for(i=0;i<sizeof(anagram);i++) 
		free(anagram[i]);
	free(anagram);
	return 0;
}

The program compiled successfully, but when I run it, it keeps getting me a Segmentation Faullt, I am using a bit confusing pointers here, so I am not quite sure where I did the mistake..
I tried gdb, and it gave me this :

Program received signal SIGSEGV, Segmentation fault.
0xb7de7613 in strlen () from /lib/tls/i686/cmov/libc.so.6

Thanks in advance.
meriororen.

[MK27]

I'm not sure where your problem is but one thing I would note (which might help to narrow this down) is that:

if(strlen(str1) != strlen(str2)) return 0;

It looks to me like these two numbers will not change for the duration of the function, so you should really put them into two variables at the beginning:

int len1 = strlen(str1), len2 = strlen(str2);

This is because the processor has to perform all the calculations everytime you call strlen. That includes every single iteration in a for loop:

for(i=0;i<strlen(str1);i++){

So if the loop runs ten times, you have ten strlen() calls instead of 0 calls with

for(i=0;i<len1;i++){

And, as mentioned, debugging gets a little easier when you minimize unnecessary function calls.

[Salem]

Well that looks like it crashed in a strlen function.

- check your use of strlen()
- think about whether any of them could have passed a bad pointer
- think about whether any of them could have been passed a valid pointer, but without a \0 in a reasonable place.

[quzah]

for(i=0;i<sizeof(anagram);i++){

What is this supposed to be doing?


Quzah.

[meriororen]

for(i=0;i<sizeof(anagram);i++){

What is this supposed to be doing?


Quzah.

it supposed to check whether the angram of the next given "input" is already inside the anagram[] array..

I check areAnags() in another program (i simply put two words as the input) and it worked, the strlen() function only exist inside areAnags(), not in main, I don't know why it worked on another program but not this.

also, I erased

 anagram[0] = strdup(input);

from the while loop, it was stupid mistake.

I put the strlen inside len1 and len2 variable, thanks to mk27.

Thanks for the advices,
However, I am still lost. I am working on it, but need some more advices. thanks

[meriororen]

ok, I found the segfault reason,

sizeof(anagram) give out 4 (as sizeof(char *) is 4).. I changed it..

but another problem came, no matter what input I gave, the result keep showing 1. ~___~

here is my current program :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 33



int areAnags(const char *str1,const char *str2){
	int i,temp;
	int count1[256] = {0}; 
	int count2[256] = {0};
	int len1 = strlen(str1), len2 = strlen(str2);

	if(len1 != len2) return 0;	

	for(i=0;i<len1;i++){
		temp = (int)str1[i];
		count1[temp]++;
	}
	for(i=0;i<len2;i++){
		temp = (int)str2[i];
		count2[temp]++;
	}

	for(i=97;i<=122;i++){
		if(count1[i] != count2[i]) return 0;	
	}
	
	return 1;
}


int main(void){
	char input[MAX];
	int count = 0,i,anagsize;
	char **anagram = NULL;
	
	anagram = malloc(sizeof(char *));
	anagram[0] = malloc(MAX * sizeof(char));
	if(anagram == NULL){
		printf("Insufficient memory available.\n");		
		return EXIT_FAILURE;
	}

	anagram[0] = " ";

	anagsize = sizeof(anagram) / sizeof(char *);
	
	while(scanf("%s", input) != EOF){	
		for(i=0;i<anagsize;i++){
			if(areAnags(anagram[i],input) == 0){
				anagram = realloc(anagram, (count+1) * sizeof(char *));
				anagram[count] = malloc((strlen(input)+1) * sizeof(char));

				if(anagram == NULL || anagram[count] == NULL){
						printf("Insufficient memory available.\n");		
						return EXIT_FAILURE;		
				}
					
				anagram[count] = strdup(input);
				count++;
			}
		}
	}

	printf("%d\n", anagsize);
	

	for(i=0;i<anagsize;i++)
		free(anagram[i]);
	free(anagram);
	return 0;
}

[linuxdude]

Your loop isn't right.

while(scanf("%s", input) != EOF){	
		for(i=0;i<anagsize;i++){
			if(areAnags(anagram[i],input) == 0){

Look at how they are getting compared. For example let's say the input is

hey
you
uoy
you
there

This is what your code is comparing everytime

hey
anagram[0] =  
input = hey
you
anagram[0] = hey
input = you
uoy  
anagram[0] = hey
input = uoy
you
anagram[0] = hey
input = you
there
anagram[0] = hey
input = there
1

The first loop compares hey to nothing! Then it never compares all of the input, just anagram[0] to input. Also, malloc calls are safer if you don't use

sizeof(type)

but rather

sizeof(pointer)

So your code would look like this

	anagram[0] = malloc(MAX * sizeof(char)); // not this
anagram[0] = malloc(MAX*sizeof(*anagram[0])); // but this

This is so if you change the type of your variable your code will still run. The FAQ is interesting.

[meriororen]

I finally could get this program to work :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 33



int areAnags(const char *str1,const char *str2){
	int i,temp;
	int count1[256] = {0};
	int count2[256] = {0};
	int len1 = strlen(str1), len2 = strlen(str2);

	if(len1 != len2) return 0;	

	for(i=0;i<len1;i++){
		temp = (int)str1[i];
		count1[temp]++;
	}
	for(i=0;i<len2;i++){
		temp = (int)str2[i];
		count2[temp]++;
	}

	for(i=97;i<=122;i++){
		if(count1[i] != count2[i]) return 0;	
	}
	
	return 1;
}

int isInside(char **array, char *string, int s){
	int i=0,in;

	while(i<s){
		if(areAnags(array[i], string) == 1){
			in = 1;
			break;
		}else{
			in = 0;
		}
		i++;
	}

	return in;
}

int main(void){
	char input[MAX];
	int count = 0,i,a_size=1;
	char **anagram;
	
	anagram = malloc(sizeof(*anagram));
	anagram[0] = malloc(MAX * sizeof(*anagram[0]));
	
	if(anagram == NULL || anagram[0] == NULL){
		printf("Insufficient memory available.\n");		
		return EXIT_FAILURE;
	}


	while(scanf("%s", input) != EOF){	
		if(isInside(anagram, input, a_size) == 0){
			anagram = realloc(anagram, (count+1) * sizeof(*anagram));
			anagram[count] = malloc((strlen(input)+1) * sizeof(*anagram[count]));

			if(anagram == NULL || anagram[count] == NULL){
					printf("Insufficient memory available.\n");		
					return EXIT_FAILURE;		
			}
				
			strncpy(anagram[count], input, strlen(input)+1);
			count++;
			a_size = count;
			printf("%s<--\n", anagram[count-1]);
		}
	}

	printf("%d\n", a_size);
	
	for(i=0;i<count-1;i++)
		free(anagram[i]);
	free(anagram);
	return 0;
}

but it seems like its lacking speed, I tried inputting word list txt file containing about 234000 words, it keeps looping till 20+ minutes run under my netbook (asus eeePC atom 1.6GHz, 1GB ram).


I wonder how to add speed to my program...

[ZaC]

I'd change the function to find anagrams... I sudgest you to sort each letter of the word, than if a sorted word like this already exists (strcmp on a list of anagrams, if you can use hash table this is a good choose) you don't store else you will store this new word. It should be faster.

[nonoob]

I wish I could help. Even just for my own amusement. Sounds like an intriguing problem but your statement of needing pairs of anagrams has me stumped. What is the program supposed to do exactly? Usually an anagram finder figures out if there are words existing containing the desired letters... "pairs" makes no sense to me.

[meriororen]

Sorry about the lack of explanation,

I am not too good to express things in English :P


The program was meant to find groups of anagrams in given words, e.g. :

file
life
run
break
brake

which would be :

{file, life}
{break, brake}
{run}

and then, the program outputs:
3 (there are 3 groups of anagrams)

Eventually, I start things over because the last program I made crazily compared everything inside the array to the next input,,

I decided to sort the inputted words into binary trees (I learnt this in one night without sleeping >.<) and succeeded reducing the execution time to 4seconds (233514 words -> 213566 groups)


thanks people!

[ZaC]

it is a good choose, but why don't you think about my suggestion?
You should not save each word but just one for each group...
From the example:

file
life
run
break
brake

here you have to save only
efil
nru
abekr
Theese are the first word of each founded group but with sorted letters.
If you sort each word before to look for it over the tree, for each group you will get the same word... I think that this saves time and memory

[nonoob]

Thanks for the additional explanation. Looks like you shouldn't need binary trees and whatnots. Here's how I would do it.

Since the input is guaranteed to contain contiguous lists of possible pairs of anagrams...

1 - Just save the first incoming word in the count1 array as you've done. (Clever!)
2 - For subsequent possible anagram word, first check if the word is the same length...
then
3- Subtract out the corresponding letters from the count1 array - if any entries try to go below zero, the anagram test fails. [means: a letter in the new word was never in the old word]

Any words failing the anagram test is candidate for possible pair of new anagram.