C++ RSS C++ RSS

Search Array for word Pattern

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Apr 2009
Posts: 147
Reputation: gretty is an unknown quantity at this point 
Solved Threads: 7
gretty gretty is offline Offline
Junior Poster

Search Array for word Pattern

 
0
  #1
Aug 17th, 2009
Hello

I have a program I am trying to make which takes in a word pattern (eg; d?ll, h?l?o, go?dby? etc) & searches an 'array containing different words' to find any words in the array that match the input word pattern.

So for example; if I input 'd?ll', the program would output

dell
dill
doll
etc....

Or if I input 'ap??e':

apace
apple
etc.......

My Problem: I am having alot of trouble thinking up an algorithm (way) to search the array to find all the words that match the word pattern.

I know how to determine whether a word has the same 'word pattern' as the input word - see my function below

I am supposed to use a binary search - see my other function, which I know how to do, but could I get some help (algorithms) on how do I mesh the 2 functions to search an array & return all the words that match the input word pattern?

Any suggestions would be greatly appreciated

Compare words Function:
C++ Syntax (Toggle Plain Text) 
  1.   bool wordComparision(string s1, string s2) {
  2.  
  3. 			 if(s1.length() != s2.length())
  4. 		return false;
  5.  
  6. 	if(!s1[0])
  7. 		return false;
  8.  
  9. 	if(s1 == s2) return true;
  10.  
  11. 	for(int i = 0; i < (int)s1.length(); i++)
  12. 	{
  13. 		// check if all the letters that occur in s1 are
  14. 		// also present in s2 & visa versa
  15. 	if(s1[i]!='?')  {
  16.  
  17. 		if(s1.find(s2[i]) == string::npos)
  18. 			return false;
  19. 		if(s2.find(s1[i]) == string::npos)
  20. 			return false;
  21. 	}
  22. 				}
  23.  
  24. 	return true;
  25. }


My Binary Search Function:
C++ Syntax (Toggle Plain Text) 
  1. bool binarySearch(string array[], string word, int begin, int end) {
  2.  
  3. 	int mid = end;
  4.  
  5. 	while (begin <= end) {
  6. 		mid = (begin + end) / 2;
  7.  
  8. 		if ( word == array[mid] ) {	 // if the loop gets to this point
  9. 			return true;				// then we have found the word we're looking for
  10. 		}
  11. 		else if (word > array[mid]) {
  12. 			begin = mid + 1;
  13. 		}
  14. 		else if (word < array[mid]) {
  15. 			end = mid - 1;
  16. 		}
  17. 	}
  18.  
  19. 	return false;					   // if we get to here the word is not in the dictionary
  20.  
  21. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 483
Reputation: DangerDev has a spectacular aura about DangerDev has a spectacular aura about 
Solved Threads: 58
DangerDev's Avatar
DangerDev DangerDev is offline Offline
Posting Pro in Training

Re: Search Array for word Pattern

 
0
  #2
Aug 17th, 2009
In this scenario binary search will not do the job, simple go for linear search. Here is algorithm:
C++ Syntax (Toggle Plain Text) 
  1. 1. take pattern as patternString.
  2. 2. take one string from string array as strToCompare
  3. 3. If patternString and strToCompare are matching then print strToCompare.
  4. 4. go for next string in array and go to step 2.
Freedom in the Mind, Faith in the words.. Pride in our Souls...
Indian Developer
http://falaque.wordpress.com/
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2008
Posts: 1,097
Reputation: firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice 
Solved Threads: 142
firstPerson's Avatar
firstPerson firstPerson is offline Offline
Veteran Poster

Re: Search Array for word Pattern

 
0
  #3
Aug 17th, 2009
I think you can just do the following :

get the user input. Find '?' character. Replace '?' character with
some other letter. Check for valid word. save it to result list.
Last edited by firstPerson; Aug 17th, 2009 at 2:38 am. 
I give up! 
1) What word becomes shorter if you add a letter to it? [ Solved by : niek_e ]
2) What does this sequence  equal to :  (.5u - .5a)(.5u-.5b)(.5u-.5c) ...
3) What is the 123456789 prime numer?
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2009
Posts: 66
Reputation: Protuberance will become famous soon enough Protuberance will become famous soon enough 
Solved Threads: 14
Protuberance's Avatar
Protuberance Protuberance is offline Offline
Junior Poster in Training

Re: Search Array for word Pattern

 
0
  #4
Aug 17th, 2009
I think you have to try use Regular expressions.
Info

So there is algorithm:
1. Get string
2. Get first word with '?' symbols
3. Get all words from the list, which have the same first letter and length
4. Through regular expressions does compare a word from a list with a word with character "?"
5. If it matches save word from list to a list of valid results

A lack of this method is the use of plenty of regular expressions.
"If a problem can be decided - it is not needed to worry, and if to decide it is impossible - worrying is useless." (с)
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

Re: Search Array for word Pattern

 
0
  #5
Aug 17th, 2009
You could still use a letter frequency counter algo here.

For example

d?ll

could be:

dlla
dllb
dllc
dlld
dlle
dllf
dllg
dllh
dlli
dllj
dllk
dlll
dllm
dlln
dllo
dllp
dllq
dllr
dlls
dllt
dllu
dllv
dllw
dllx
dlly
dllz

Of course the worse case scenario is when you get something like ????????? which would have a poor time complexity. You could improve the algo.
Last edited by iamthwee; Aug 17th, 2009 at 10:20 am.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 44
Reputation: zalezog is an unknown quantity at this point 
Solved Threads: 11
zalezog zalezog is offline Offline
Light Poster

Re: Search Array for word Pattern

 
0
  #6
Aug 17th, 2009
•
•
•
•
Originally Posted by gretty
I am supposed to use a binary search ...
Binary Search would come into picture only iff you have a sorted input like dell, bell etc and corresponding sorted array to search for. Your examples don't have a sorted string in most of the cases.

But if we had to go without binary search, then the function would be something like this:
c++ Syntax (Toggle Plain Text) 
  1. //indicator being the missing character '?' or '*' or something else 
  2. //s1 being an element of the string array and s2 is the string 
  3. //with indicator in it
  4. bool wordComparison(string s1, string s2, char indicator) {
  5.       if(s1.length() != s2.length())
  6.           return false;
  7.       if(!s1[0])
  8.          return false;
  9.       if(s1 == s2)
  10.           return true;
  11.  
  12.       for (int i = 0; i < s1.length(); i++) {
  13.           if (s2[i] != indicator &&  (s1[i] != s2[i]))
  14.               return false;
  15.  
  16.       }
  17.       return true;
  18.  }
Last edited by zalezog; Aug 17th, 2009 at 11:17 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 672
Reputation: Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold 
Solved Threads: 99
Sky Diploma's Avatar
Sky Diploma Sky Diploma is offline Offline
Practically a Master Poster

Re: Search Array for word Pattern

 
0
  #7
Aug 17th, 2009
I think that we might basically sort your array according to the length of the word.

Then The Binary Search Would get you to one of the bounds of the SearchList containing the same length,

Then I guess You can take in the corresponding letters and compare to their equivallents, if all of them match. then its probably the word.

Or Else another alternate method of finding matches would be to first use the Binary Search to make a mini list of all the words with the probable length. And sort the mini array.

Then With the first known character....... for ex :: GIVEN WORD ?ar?

You could use the Binary Search to go through all the words to find the words with 'a' in the second position. Out of that mini list, you will next go for the next character until all the characters are exhausted.

This is something like a sieve. But far more complex.
1. Please Mark Your Thread as Solved After Getting Your Answers.
2. Please Use CODE TAGS .
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2009
Posts: 147
Reputation: gretty is an unknown quantity at this point 
Solved Threads: 7
gretty gretty is offline Offline
Junior Poster

Re: Search Array for word Pattern

 
0
  #8
Aug 19th, 2009
Thanks for your help guys

I've got the major parts sorted out, identify if a word fits the word pattern, I just dont know how to search the Array of words efficiently(timewise).

I have an array that is 130,000 words, yes thats right, 130,000, & the words are all in alphabetical order. So would you guys suggest a binary search is the way to go, or is there a different way to search the array I dont know of.

Could anyone help me alter my search Function from a selection sort to a Binary search?

Below is my code which uses a selection sort/search method:
C++ Syntax (Toggle Plain Text) 
  1. void search(string array[], int a_size, string w) {
  2.  
  3. // array[] = an array of words in alphabetical order
  4. // a_size = array's size which is over 130,000
  5.  
  6. 	for (int i=0; i<a_size; i++) {
  7. 		if (array[i].length() == w.length()) {
  8. 			if (wordPattern(w,array[i]))
  9. 				cout << array[i] << "\n";
  10. 		}
  11. 	}
  12. }
  13.  
  14. bool wordPattern(string w1, string w2) {
  15.  
  16. 	for (int i=0; i<(int)w1.size();i++)
  17. 	{
  18. 		if (w1[i]!='?') {
  19. 			size_t  val= w2.find(w1[i]);
  20. 			if(val==string::npos) { return false; }
  21. 			else                  { w2.erase(val,1); }
  22. 		}
  23. 	}
  24. 	return true;
  25.  
  26. }

Entire Program
C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. void to_lower(string& a);
  7. void search(string array[], int a_size, string w);
  8. bool wordPattern(string w1, string w2);
  9.  
  10. int main() {
  11. 	string word;
  12. 	string a[] = {"feig", "frab", "frae", "fram", "frap", "frat", "fray", "freedom", "fret", "fribalis"};
  13.  
  14. 	cout << "Enter a word pattern: " << flush;
  15. 	cin >> word;
  16.  
  17. 	to_lower(word);
  18. 	search(a,10,word);
  19.  
  20. 	return 0;
  21. }
  22.  
  23. void to_lower(string& s) {
  24.  
  25. 	for (int i=0; i<(int)s.length(); i++) {
  26. 		s[i] = tolower(s[i]);
  27. 	}
  28. }
  29.  
  30. void search(string array[], int a_size, string w) {
  31.  
  32. 	for (int i=0; i<a_size; i++) {
  33. 		if (array[i].length() == w.length()) {
  34. 			if (wordPattern(w,array[i]))
  35. 				cout << array[i] << "\n";
  36. 		}
  37. 	}
  38. }
  39.  
  40. bool wordPattern(string w1, string w2) {
  41.  
  42. 	for (int i=0; i<(int)w1.size();i++)
  43. 	{
  44. 		if (w1[i]!='?') {
  45. 			size_t  val= w2.find(w1[i]);
  46. 			if(val==string::npos) { return false; }
  47. 			else                  { w2.erase(val,1); }
  48. 		}
  49. 	}
  50. 	return true;
  51.  
  52. }
Last edited by gretty; Aug 19th, 2009 at 12:13 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,810
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 501
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster

Re: Search Array for word Pattern

 
0
  #9
Aug 19th, 2009
If you are searching for a word, the fact that the array is alphabetically sorted would be useful and a binary search would be the way to go. But you're not searching for a word, you're searching for a regular expression within the word. You're also searching for ALL words that contain that regular expression, so it seems to me that you have to check every single word, whether the array is sorted or not. So don't bother sorting them and don't bother with a binary search. Or if you sort them, sort them by length, like Sky Diploma suggested. That might be of some use because you can immediately skip words that are too short. But I don't see any place for binary search.

From first post:

•
•
•
•
I am supposed to use a binary search
Why?
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array based beginner binary c++ c/c++ calculator char char* class classes code compile compiler console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news node numbertoword output parameter pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings struct temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC