Ad:

C++ Discussion Thread
Unsolved
Views: 2087

Aug 17th, 2009

Search Array for word Pattern

Expand Post »

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)
  bool wordComparision(string s1, string s2) {
 
			 if(s1.length() != s2.length())
		return false;
 
	if(!s1[0])
		return false;
 
	if(s1 == s2) return true;
 
	for(int i = 0; i < (int)s1.length(); i++)
	{
		// check if all the letters that occur in s1 are
		// also present in s2 & visa versa
	if(s1[i]!='?')  {
 
		if(s1.find(s2[i]) == string::npos)
			return false;
		if(s2.find(s1[i]) == string::npos)
			return false;
	}
				}
 
	return true;
}
  bool wordComparision(string s1, string s2) {

			 if(s1.length() != s2.length())
		return false;

	if(!s1[0])
		return false;

	if(s1 == s2) return true;

	for(int i = 0; i < (int)s1.length(); i++)
	{
		// check if all the letters that occur in s1 are
		// also present in s2 & visa versa
	if(s1[i]!='?')  {

		if(s1.find(s2[i]) == string::npos)
			return false;
		if(s2.find(s1[i]) == string::npos)
			return false;
	}
				}

	return true;
}

My Binary Search Function:

C++ Syntax (Toggle Plain Text)
bool binarySearch(string array[], string word, int begin, int end) {
 
	int mid = end;
 
	while (begin <= end) {
		mid = (begin + end) / 2;
 
		if ( word == array[mid] ) {	 // if the loop gets to this point
			return true;				// then we have found the word we're looking for
		}
		else if (word > array[mid]) {
			begin = mid + 1;
		}
		else if (word < array[mid]) {
			end = mid - 1;
		}
	}
 
	return false;					   // if we get to here the word is not in the dictionary
 
}
bool binarySearch(string array[], string word, int begin, int end) {

	int mid = end;

	while (begin <= end) {
		mid = (begin + end) / 2;

		if ( word == array[mid] ) {	 // if the loop gets to this point
			return true;				// then we have found the word we're looking for
		}
		else if (word > array[mid]) {
			begin = mid + 1;
		}
		else if (word < array[mid]) {
			end = mid - 1;
		}
	}

	return false;					   // if we get to here the word is not in the dictionary

}

Similar Threads

sort and search in array of objects in C++
Search file for a word and read the next word? in C++
Search an array of objects. in C++
Call a function at RUNTIME in C++
Trying to creating an array from a text file in C++

gretty

Reputation Points: 10

Solved Threads: 7

Junior Poster

Offline

158 posts
since Apr 2009

Permalink

Aug 17th, 2009

Re: Search Array for word Pattern

In this scenario binary search will not do the job, simple go for linear search. Here is algorithm:

C++ Syntax (Toggle Plain Text)
take pattern as patternString.
take one string from string array as strToCompare
If patternString and strToCompare are matching then print strToCompare.
go for next string in array and go to step 2.
take pattern as patternString.
take one string from string array as strToCompare
If patternString and strToCompare are matching then print strToCompare.
go for next string in array and go to step 2.

DangerDev

Reputation Points: 165

Solved Threads: 59

Posting Pro in Training

Offline

485 posts
since Jan 2008

Permalink

Aug 17th, 2009

Re: Search Array for word Pattern

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.

firstPerson

Reputation Points: 840

Solved Threads: 594

Senior Poster

Offline

3,862 posts
since Dec 2008

Permalink

Aug 17th, 2009

Re: Search Array for word Pattern

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.

Protuberance

Reputation Points: 78

Solved Threads: 17

Junior Poster in Training

Offline

88 posts
since Aug 2009

Permalink

Aug 17th, 2009

Re: Search Array for word Pattern

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.

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Aug 17th, 2009

Re: Search Array for word Pattern

Quote 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)
//indicator being the missing character '?' or '*' or something else 
//s1 being an element of the string array and s2 is the string 
//with indicator in it
bool wordComparison(string s1, string s2, char indicator) {
      if(s1.length() != s2.length())
          return false;
      if(!s1[0])
         return false;
      if(s1 == s2)
          return true;
 
      for (int i = 0; i < s1.length(); i++) {
          if (s2[i] != indicator &&  (s1[i] != s2[i]))
              return false;
 
      }
      return true;
 }
//indicator being the missing character '?' or '*' or something else 
//s1 being an element of the string array and s2 is the string 
//with indicator in it
bool wordComparison(string s1, string s2, char indicator) {
      if(s1.length() != s2.length())
          return false;
      if(!s1[0])
         return false;
      if(s1 == s2)
          return true;

      for (int i = 0; i < s1.length(); i++) {
          if (s2[i] != indicator &&  (s1[i] != s2[i]))
              return false;

      }
      return true;
 }

Last edited by zalezog; Aug 17th, 2009 at 11:17 am.

zalezog

Reputation Points: 53

Solved Threads: 13

Light Poster

Offline

47 posts
since Oct 2008

Permalink

Aug 17th, 2009

Re: Search Array for word Pattern

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.

Sky Diploma

Reputation Points: 673

Solved Threads: 125

Practically a Posting Shark

Offline

818 posts
since Mar 2008

Permalink

Aug 19th, 2009

Re: Search Array for word Pattern

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)
void search(string array[], int a_size, string w) {
 
// array[] = an array of words in alphabetical order
// a_size = array's size which is over 130,000
 
	for (int i=0; i<a_size; i++) {
		if (array[i].length() == w.length()) {
			if (wordPattern(w,array[i]))
				cout << array[i] << "\n";
		}
	}
}
 
bool wordPattern(string w1, string w2) {
 
	for (int i=0; i<(int)w1.size();i++)
	{
		if (w1[i]!='?') {
			size_t  val= w2.find(w1[i]);
			if(val==string::npos) { return false; }
			else                  { w2.erase(val,1); }
		}
	}
	return true;
 
}
void search(string array[], int a_size, string w) {

// array[] = an array of words in alphabetical order
// a_size = array's size which is over 130,000

	for (int i=0; i<a_size; i++) {
		if (array[i].length() == w.length()) {
			if (wordPattern(w,array[i]))
				cout << array[i] << "\n";
		}
	}
}

bool wordPattern(string w1, string w2) {

	for (int i=0; i<(int)w1.size();i++)
	{
		if (w1[i]!='?') {
			size_t  val= w2.find(w1[i]);
			if(val==string::npos) { return false; }
			else                  { w2.erase(val,1); }
		}
	}
	return true;

}

Entire Program

C++ Syntax (Toggle Plain Text)
#include <iostream>
#include <string>
 
using namespace std;
 
void to_lower(string& a);
void search(string array[], int a_size, string w);
bool wordPattern(string w1, string w2);
 
int main() {
	string word;
	string a[] = {"feig", "frab", "frae", "fram", "frap", "frat", "fray", "freedom", "fret", "fribalis"};
 
	cout << "Enter a word pattern: " << flush;
	cin >> word;
 
	to_lower(word);
	search(a,10,word);
 
	return 0;
}
 
void to_lower(string& s) {
 
	for (int i=0; i<(int)s.length(); i++) {
		s[i] = tolower(s[i]);
	}
}
 
void search(string array[], int a_size, string w) {
 
	for (int i=0; i<a_size; i++) {
		if (array[i].length() == w.length()) {
			if (wordPattern(w,array[i]))
				cout << array[i] << "\n";
		}
	}
}
 
bool wordPattern(string w1, string w2) {
 
	for (int i=0; i<(int)w1.size();i++)
	{
		if (w1[i]!='?') {
			size_t  val= w2.find(w1[i]);
			if(val==string::npos) { return false; }
			else                  { w2.erase(val,1); }
		}
	}
	return true;
 
}
#include <iostream>
#include <string>

using namespace std;

void to_lower(string& a);
void search(string array[], int a_size, string w);
bool wordPattern(string w1, string w2);

int main() {
	string word;
	string a[] = {"feig", "frab", "frae", "fram", "frap", "frat", "fray", "freedom", "fret", "fribalis"};

	cout << "Enter a word pattern: " << flush;
	cin >> word;

	to_lower(word);
	search(a,10,word);

	return 0;
}

void to_lower(string& s) {

	for (int i=0; i<(int)s.length(); i++) {
		s[i] = tolower(s[i]);
	}
}

void search(string array[], int a_size, string w) {

	for (int i=0; i<a_size; i++) {
		if (array[i].length() == w.length()) {
			if (wordPattern(w,array[i]))
				cout << array[i] << "\n";
		}
	}
}

bool wordPattern(string w1, string w2) {

	for (int i=0; i<(int)w1.size();i++)
	{
		if (w1[i]!='?') {
			size_t  val= w2.find(w1[i]);
			if(val==string::npos) { return false; }
			else                  { w2.erase(val,1); }
		}
	}
	return true;

}

Last edited by gretty; Aug 19th, 2009 at 12:13 am.

gretty

Reputation Points: 10

Solved Threads: 7

Junior Poster

Offline

158 posts
since Apr 2009

Permalink

Aug 19th, 2009

Re: Search Array for word Pattern

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:

Quote ...

I am supposed to use a binary search

Why?

VernonDozier

Featured Poster

Reputation Points: 2614

Solved Threads: 687

Posting Expert

Offline

5,372 posts
since Jan 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: changing the text in the head bar of a window.

Next Thread in C++ Forum Timeline: implementation of the copy constructor,operators [ ],-,+,=,!=...its urgent

DaniWeb Message

Cancel Changes

User Name
Password