string manipulations

[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:)

*** Sent via Developersdex http://www.developersdex.com ***

[Barry Kelly]

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/

[Michael A. Covington]

"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...

[Christof Nordiek]

"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

[Luc E. Mistiaen]

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/

[Barry Kelly]

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/