By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,149 Members | 1,335 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
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" <cs*******@yahoo.comwrote in message
news:e5**************@TK2MSFTNGP05.phx.gbl...
>
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" <ba***********@gmail.comschrieb im Newsbeitrag
news:4a********************************@4ax.com...
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).
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" <ba***********@gmail.comwrote in message
news:4a********************************@4ax.com...
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 #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.