 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / April 2005Big O and algorithm to decide string A contains string B?
I need to implement a function to return True/false whether String A contains String B. For example, String A = "This is a test"; String B = "is is". So it will return TRUE if String A includes two "i" and two "s". The function should also handle if String A and B have huge values, like two big dictionary. What's the best approach to achieve this with the best performance? what's the Big O then? I am thinking to put A and B into two hashtable, like key = "i" and value = "2" and so on. Then compare these two hashtable. But how to compare two hashtables? Please advise. > I need to implement a function to return True/false whether String A > contains String B. For example, String A = "This is a test"; String B = [quoted text clipped - 8 lines] > value = "2" and so on. Then compare these two hashtable. But how to > compare two hashtables? Please advise. One simple possibility is to iterate through each position i within string A and see if the substring A(i,i+length(B)) = B. Java and C++ have facilities to make this quite simple. The worst case runtime is O(length(A)*length(B)) under reasonable assumptions about how string comparisons are performed. Perhaps one can do better if one is clever. <usgog@yahoo.com> wrote in message > I need to implement a function to return True/false whether String A > contains String B. For example, String A = "This is a test"; String B = > "is is". So it will return TRUE if String A includes two "i" and two > "s". The function should also handle if String A and B have huge > values, like two big dictionary. Because String B = "is is" (note the space), should the function return true if String A contains two "i", two "s", one space? The first step would be to parse String B so that we know to expect 2 "i", 2 "s", 1 " ". What's the number of distinct chars? Is it A-Z and a-z for a total of 52? If the number of distinct chars is small, say 256 distinct chars, create an array, such as unsigned expect[256], to represent the number of chars to expect. expect['i'] would equal 2, expect['s'] would equal 2, expect[' '] would equal 1, and all other expect elements would be zero. If the number of distinct chars is large, then you could use a map<char_type, unsigned> or hashtable. Now step through every char in String A. Let the char in question be char c. Decrement expect[c] by one, but if it is zero then don't decrement it. Now check if all the elements in expect are zero. As an optimization, you only need to do this check if you decremented expect[c]. To check if all the elements in expect are zero, you could for example create another array zero, such as unsigned zero[256] = {0}, and use memcmp to compare expect to zero. There are other ways, maybe platform specific ways that might be faster. Remember to deal with the special case that String B is the empty string, in which case you can probably immediately return true. > What's the best approach to achieve this with the best performance? > what's the Big O then? My algorithm is O(length(String A)) + O(length(String B)). > I am thinking to put A and B into two hashtable, like key = "i" and > value = "2" and so on. Then compare these two hashtable. But how to > compare two hashtables? Please advise. In principle it is doable, but putting all the chars of String A into a hashtable might be rather expensive. To compare two hashtables, you could iterate through the elements in the first hash table, using a for_each(hash1.begin(), hash1.end()) structure, or even for (Iter iter = hash1.begin(); iter != hash1.end(); ++iter). For each element in hash1, look up the corresponding value in hash2, for example hash2[iter->key]. Then check if the values are equal, for example iter->value == hash2[iter->key]. I do not quite undertstand the problem. You write that the function should return true when string A contains string B. But your example shows that it should return true when string A contains all characters that are in string B. This is something very different. Which one is your problem? cheers, Marcin Kalicinski >I need to implement a function to return True/false whether String A > contains String B. For example, String A = "This is a test"; String [quoted text clipped - 9 lines] > value = "2" and so on. Then compare these two hashtable. But how to > compare two hashtables? Please advise. bool XY(const char* src, const char* seek) { std::map<char, int> counter; std::map<char, int>::iterator it; // Fill map with number of chars in dest for(; *seek!='\0'; ++seek) { if(is_char_to_be_counted(*seek)) ++counter[*seek]; } // subtract the count of these chars on src for(; *src!='\0'; ++src) { it = counter.find(*src); if(it!=counter.end() && --it->second<0) return false; // src has more 'x's than dest } // See if any of these has different count for(it=counter.begin(); it!=counter.end(); ++it) { if(it->second) return false; // dest has more 'x's than src } return true; } this should so the trick quickly. If you really have chars, you can replace the std::map with a simple array of 256 ints... -Gernot Acutally the problem is not about String Matching. The function will return TRUE if string A contains all characters that are in string B. Or String A has what String B has. For example, String B is "issi" and String A is "This is a test", the function will return TRUE. So what if String A and B have big values, what's the best algorithm and Big O to achieve this? I am thinking creating two hashtable. For String B, key=i, value=2; key=s, value=2. For String A, key=i, value=2; key=s, value=3, etc. Then compare this two hashtable. So constructing these two hashtable will be expensive but the Big O will be O(nlogn). Is it good? ) Acutally the problem is not about String Matching. The function will ) return TRUE if string A contains all characters ) that are in string B. Or String A has what String B has. For example, ) String B is "issi" and String A is "This is a test", the function will ) return TRUE. So what if String A and B have big values, what's the best ) algorithm and Big O to achieve this? ) ) I am thinking creating two hashtable. For String B, key=i, value=2; ) key=s, value=2. For String A, key=i, value=2; key=s, value=3, etc. Then ) compare this two hashtable. So constructing these two hashtable will be ) expensive but the Big O will be O(nlogn). Is it good? Why a hashtable ? There are only 256 different characters, so you can just make an array with 256 entries and count. The BigO will be O(n). SaSW, Willem  SignatureDisclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Yes. An array with 256 entries should be enough. But how to create an array using char as the index? array index is supposed to be int, right? For example, array[0] = 'a' instead of array['a'] = 0. Sorry, I am a newbie to algorithm... > Yes. An array with 256 entries should be enough. But how to create an > array using char as the index? array index is supposed to be int, > right? a char is nothing more then a small integer in C and C++. Only during input and output a char is treated differently. > For example, array[0] = 'a' instead of array['a'] = 0. Sorry, I > am a newbie to algorithm... array['a'] = 0; is fine. (Remember: a char is nothing more then an small integer. Its value is the code number of the character on your system). SignatureKarl Heinz Buchegger kbuchegg@gascad.at > Yes. An array with 256 entries should be enough. But how to create an > array using char as the index? array index is supposed to be int, > right? For example, array[0] = 'a' instead of array['a'] = 0. Sorry, I > am a newbie to algorithm... char is an integral type, like short, int and long. They'll convert without problems. i.e. int frequency[ 1<<CHAR_BIT ] = {0}; // typically 256 entries std::string A = foo(); for( int i=0;i!=A.size(); ++i ) ++frequency[ A[i] ]; std::string B = bar(); for( int i=0;i!=B.size(); ++i ) if( frequency[ B[i] ]-- == 0 ) std::cout << "B not in A"; Obvious O(A.size+B.size) and you can't do better in general. HTH, Michiel Salters > > Yes. An array with 256 entries should be enough. But how to create an > > array using char as the index? array index is supposed to be int, [quoted text clipped - 20 lines] > HTH, > Michiel Salters std:string is represented as 'char's which can be signed or unsigned depending on the platform, so you probably want e.g. ++frequency[A[i] & 0xff]. -- Roger > ) Acutally the problem is not about String Matching. The function will > ) return TRUE if string A contains all characters [quoted text clipped - 14 lines] > > SaSW, Willem You cross post this in a Jav newsgroup and have the cheek to suggest that there are only 256 characters ! That's why I abandoned C and it's derivatives... which simply assumed that nobody in China, Japan, Korea etc would ever need to use a computer ;-) > > ) Acutally the problem is not about String Matching. The function will > > ) return TRUE if string A contains all characters [quoted text clipped - 25 lines] > derivatives... which simply assumed that nobody in China, Japan, Korea etc > would ever need to use a computer ;-) No, C just assumes that people in China, Japan, Korea, and India will use computers in English!!! ;-) -- +----------------------------------------------------------------+ | Charles and Francis Richmond It is moral cowardice to leave | | undone what one perceives right | | richmond at plano dot net to do. -- Confucius | +----------------------------------------------------------------+ > From: "Pointless Harlows" <pointless_nopinkmeat@btinternet.com> > You cross post this in a Jav newsgroup and have the cheek to suggest > that there are only 256 characters ! The original poster included a C++ group, where 8-bit characters are generally assumed, and the example shown is purely ASCII, so it was a natural assumption that "character" meant either 7-bit ASCII stored in 8-bit bytes with high bit zero or 8-bit extended-ASCII with platform-dependent semantics such as latin-1. However you have a good point that it was *also* posted to a Java group, where the original characters were a 16-bit subset of Unicode and later changed to UTF-16 and even more recently redefined as 32-bit bytes. With so many possible characters, it's hopelessly slow to build a lookup table. But a map (hashtable or binary tree) isn't necessary if the data consists of text from any natural language or combination thereof. A very few characters appear very commonly, such as space and 'e' and 't' in English, while the majority of characters almost never appear. The optimum data structure might be a simple linear list, with linear search, sorted per descending occurance count, so that most searches reach their target very quickly. When you put a new character in the table, you put it after the last already-existing character. When you increment a count of an old character, you bubble it forward if its count now exceeds its predecessor's count. After you've finished building a table from a string, if you want to use it as a lookup table for comparing two such tables, and it's too large to efficiently search linearily, you can then sort it by UniCode value so as to be able to use binary search for the lookups. But in most practical cases continuing to do linear lookup should be fast enough. Actually, the time to build the table is larger than the time to scan it once, so don't bother sorting it unless the string you've scanned is constant and the linear-search table is large and you'll be comparing it many times. By the way, the Subject field is misleading. What you really are doing is testing whether multiset B is subset of multiset A, where the elements happen to be characters and they happen to be given as parameters as if they were strings. So one obvious way to solve the problem is to convert each string to an explicit multiset, discarding all sequence information from the strings, then compare the multisets. In some programming languages there might already be a built-in API method for comparing multisets, something like static boolean isSubsetOf(MultiSet B, MultiSet A); or [instance method] boolean isSubsetOf(MultiSet A); not to mention a constructor that converts from strings: MultiSet(String s); Although I've written those as if part of the Java API, whether anything resembling that is already in the Java API is unknown to me and not worth checking right now. But anybody actually planning to implement the algorithm in Java should check the API documentation to see if anything like it is available before re-inventing the wheel yourself. (See also the thread on reusable software components.) Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.