455,149 Members | 1,335 Online Need help? Post your question and get tips & solutions from a community of 455,149 IT Pros & Developers. It's quick & easy.

# string manipulations

 P: n/a Hello , I need to perform the following operation: There are two strings (str1 and strSet) ,I need to write a function which will get str1 and strSet and will return an index of the first occurrence of a character in str1 that belongs to the set of characters in strSet. I need to perform it with complexity of O(m+n) /n-str lenght ,m-strSet lenght. For example: str="fsaghj" strSet="bya" the output will be 3 (the index of "a" in str). How can I do it? Thanks a lot:) *** Sent via Developersdex http://www.developersdex.com *** Jan 28 '07 #1
5 Replies

 P: n/a csharpula csharp wrote: I need to perform the following operation: There are two strings (str1 and strSet) ,I need to write a function which will get str1 and strSet and will return an index of the first occurrence of a character in str1 that belongs to the set of characters in strSet. I need to perform it with complexity of O(m+n) /n-str lenght ,m-strSet lenght. For example: str="fsaghj" strSet="bya" the output will be 3 (the index of "a" in str). That sounds like a homework question. How can I do it? Well, a simple-minded nested loop, iterating over str then strSet, would have complexity of O(m*n), so obviously that's out. However, if you added the characters in strSet to a structure that had O(1) lookup behaviour, such as a trie or hash, then you'd be able to do the adding in O(m) and the main loop through str in O(n) for a total of O(m+n). -- Barry -- http://barrkel.blogspot.com/ Jan 29 '07 #2

 P: n/a "csharpula csharp" Hello , I need to perform the following operation: There are two strings (str1 and strSet) ,I need to write a function which will get str1 and strSet and will return an index of the first occurrence of a character in str1 that belongs to the set of characters in strSet. I need to perform it with complexity of O(m+n) /n-str lenght ,m-strSet lenght. For example: str="fsaghj" strSet="bya" the output will be 3 (the index of "a" in str). How can I do it? Thanks a lot:) Be sure to acknowledge us when you turn in your homework... Jan 29 '07 #3

 P: n/a "Barry Kelly" I need to perform the following operation:There are two strings (str1 and strSet) ,I need to write a functionwhich will get str1 and strSet and will return an index of the firstoccurrence of a character in str1 that belongs to the set of charactersin strSet.I need to perform it with complexity of O(m+n) /n-str lenght ,m-strSetlenght.For example: str="fsaghj" strSet="bya" the output will be 3 (the indexof "a" in str). That sounds like a homework question. >How can I do it? Well, a simple-minded nested loop, iterating over str then strSet, would have complexity of O(m*n), so obviously that's out. However, if you added the characters in strSet to a structure that had O(1) lookup behaviour, such as a trie or hash, then you'd be able to do the adding in O(m) and the main loop through str in O(n) for a total of O(m+n). wouldn't that have complexity O(log(m)(m+n)) ? Christof Jan 29 '07 #4

 P: n/a In .NET I would use the string function 'IndexOfAny'. However the doc doesn't say what is its complexity. /LM "Barry Kelly" I need to perform the following operation:There are two strings (str1 and strSet) ,I need to write a functionwhich will get str1 and strSet and will return an index of the firstoccurrence of a character in str1 that belongs to the set of charactersin strSet.I need to perform it with complexity of O(m+n) /n-str lenght ,m-strSetlenght.For example: str="fsaghj" strSet="bya" the output will be 3 (the indexof "a" in str). That sounds like a homework question. >How can I do it? Well, a simple-minded nested loop, iterating over str then strSet, would have complexity of O(m*n), so obviously that's out. However, if you added the characters in strSet to a structure that had O(1) lookup behaviour, such as a trie or hash, then you'd be able to do the adding in O(m) and the main loop through str in O(n) for a total of O(m+n). -- Barry -- http://barrkel.blogspot.com/ Jan 29 '07 #5

 P: n/a Christof Nordiek wrote: Well, a simple-minded nested loop, iterating over str then strSet, would have complexity of O(m*n), so obviously that's out. However, if you added the characters in strSet to a structure that had O(1) lookup behaviour, such as a trie or hash, then you'd be able to do the adding in O(m) and the main loop through str in O(n) for a total of O(m+n). wouldn't that have complexity O(log(m)(m+n)) ? For a hash, insertion is constant time. I mentioned trie but since lookup in this case is always a single character, it would only be reasonable to use a single array, rather than a tree, so again it would be constant time. -- Barry -- http://barrkel.blogspot.com/ Jan 29 '07 #6

### This discussion thread is closed

Replies have been disabled for this discussion. 