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

 

[Barry Kelly]

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

 

[Michael A. Covington]

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]

That sounds like a homework question.


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]

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