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 *** 5  1536 
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/
"csharpula csharp" <cs*******@yaho o.comwrote in message
news:e5******** ******@TK2MSFTN GP05.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...
"Barry Kelly" <ba***********@ gmail.comschrie b im Newsbeitrag
news:4a******** *************** *********@4ax.c om...
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
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.c om...
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/
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/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Zach Tong |
last post by:
I recently ran our code through a profiler to determine why it was
using so much memory. It turns out the System.String object is taking
95% of the memory. We have considered converting the strings to
StringBuilder objects, but I don't think this will help. From what I
understand, the StringBuilder only helps with speed increases (by
reducing time to create a new string). In addition to that, most of
the string manipulations are very...
|
by: Derek |
last post by:
I'm curious about the performance of string::c_str,
so I'm wondering how it's commonly implemented. Do
most std::string implementations just keep an extra
char allocated for the NULL termination so they can
return a pointer to their internal buffer, or are
they equally likely to create a new buffer on demand?
I know the standard doesn't require any particular
implementation, which is why I'm curious if there is
a consensus among...
|
by: Dave Reid |
last post by:
Hi everyone...
I'm pretty much a newbie C++ user, and I've run into a problem.
I'm trying to read in a large text file, and then do manipulations on
it. I can read it into a large 2-dimensional character array, but I'd
really like to read it into a vector of strings. Here's how I'm doing
the read into the char array:
int main() {
string str1("booger");
string str2("test");
|
by: Jami Bradley |
last post by:
Hi,
I'm looking for an efficient way to do this, because I know it will be heavily used :-)
I have a fixed width string and I need to substitute a substring of characters with new values. I
can do this with 2 substring calls, but it will need to rebuild the string just to write a few
characters.
Here is the simple, but inefficient, version:
string s = "0123456789";
|
by: Faraz |
last post by:
Hi,
I am working with DOM and I need to do the following:
<sequence>
<element name="input1" type="string"/>
<element name="input2" type="string"/>
<element name="input3" type="string"/>
</sequence>
| | |
by: news.microsoft.com |
last post by:
What is the best way to avoid string manipulations with SQL?
I have edit box control where database is opened for attacks through SQL
commands.
Something like this:
selectString = "SELECT FIRSTNAME, LASTNAME FROM xxxTable WHERE
FIRSTNAME='"+txtTextBox1.Text"'";
Furthermore I would like to avoid of using some characters like ;:,. etc.
|
by: tshad |
last post by:
Can you do a search for more that one string in another string?
Something like:
someString.IndexOf("something1","something2","something3",0)
or would you have to do something like:
if ((someString.IndexOf("something1",0) >= 0) ||
((someString.IndexOf("something2",0) >= 0) ||
|
by: zoro |
last post by:
Hi,
I am new to C#, coming from Delphi. In Delphi, I am using a 3rd party
string handling library that includes some very useful string
functions, in particular I'm interested in BEFORE (return substring
before a pattern), AFTER (return substring after a pattern), and
BETWEEN (return substring between 2 patterns).
My questions are:
1. Can any tell me how I can implement such functionality in C#?
2. Is it possible to add/include function...
|
by: Tee |
last post by:
String Builder & String, what's the difference.
and when to use which ?
Thanks.
|
by: ma |
last post by:
Hello,
I want to change one character in a string to a new character. How can i
do this. For example I have a string called x and it contains "This is a
test" and I want to change the i in is to a so after change it become "This
as a test". I tried the following code without any sucess:
public void ChangeChar(int index,char NewChar)
{
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| | |
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| | |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
