Finding occurences of many strings in another

[Spondishy]

This is probably more of a algo question than specifically c# (although
a c# solution would be great.

I'm trying to parse a string and ensure that at least one occurence of
a number of other strings within the main string. These must not
overlap. For example, if I had the string...

"The cow jumped over the moon"

and was looking for "cow", "over", "moon" that would pass as all
phrases are in there at least once with no overlaps.

If I looked for "cow", "jumped", "jumped over" that would fail as
"jumped" and "jumped over" overlap.

Although if the phrase was

"The cow jumped and and she jumped over the moon"

"cow", "jumped", "jumped over" would pass.

Any help appreciated.

[Andrew Kirillov]

Hello

You can use the very simple algorithm for it. It will work for all provided
by you cases.

string source = "The cow jumped over the moon";
//string source = "The cow jumped and and she jumped over the moon";
string[] needles = new string[] {"cow", "jumped", "jumped over"};

foreach (string needle in needles)
{
int pos = source.IndexOf(needle);

if (pos > 0)
{
System.Diagnostics.Debug.WriteLine("found: " + needle);

source = source.Remove(pos, needle.Length);
}
}

--
With best regards,
Andrew

http://www.codeproject.com/script/pr...asp?id=1181072
"Spondishy" <sp*******@tiscali.co.uk> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...

This is probably more of a algo question than specifically c# (although
a c# solution would be great.

I'm trying to parse a string and ensure that at least one occurence of
a number of other strings within the main string. These must not
overlap. For example, if I had the string...

"The cow jumped over the moon"

and was looking for "cow", "over", "moon" that would pass as all
phrases are in there at least once with no overlaps.

If I looked for "cow", "jumped", "jumped over" that would fail as
"jumped" and "jumped over" overlap.

Although if the phrase was

"The cow jumped and and she jumped over the moon"

"cow", "jumped", "jumped over" would pass.

Any help appreciated.

[Andrew Kirillov]

Hello

You can use the very simple algorithm for it. It will work for all provided
by you cases.

string source = "The cow jumped over the moon";
//string source = "The cow jumped and and she jumped over the moon";
string[] needles = new string[] {"cow", "jumped", "jumped over"};

foreach (string needle in needles)
{
int pos = source.IndexOf(needle);

if (pos > 0)
{
System.Diagnostics.Debug.WriteLine("found: " + needle);

source = source.Remove(pos, needle.Length);
}
}

--
With best regards,
Andrew

http://www.codeproject.com/script/pr...asp?id=1181072
"Spondishy" <sp*******@tiscali.co.uk> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...

This is probably more of a algo question than specifically c# (although
a c# solution would be great.

I'm trying to parse a string and ensure that at least one occurence of
a number of other strings within the main string. These must not
overlap. For example, if I had the string...

"The cow jumped over the moon"

and was looking for "cow", "over", "moon" that would pass as all
phrases are in there at least once with no overlaps.

If I looked for "cow", "jumped", "jumped over" that would fail as
"jumped" and "jumped over" overlap.

Although if the phrase was

"The cow jumped and and she jumped over the moon"

"cow", "jumped", "jumped over" would pass.

Any help appreciated.

[Spondishy]

Thanks for the quick response. To add more complexity what if the
string was

string source = "The cow jumped over the moon and then jumped higher";
string[] needles = new string[] {"cow", "jumped", "jumped over"};

This should pass because "jumped" and "jumped over" occur in the
original string.

[Spondishy]

Thanks for the quick response. To add more complexity what if the
string was

string source = "The cow jumped over the moon and then jumped higher";
string[] needles = new string[] {"cow", "jumped", "jumped over"};

This should pass because "jumped" and "jumped over" occur in the
original string.

[gmiley]

You can use the following, and even with some modification you could
have it return a list of non-matches instead of bool.
public bool TestString(string[] testForStrings, string testString)
{
System.Collections.Hashtable testHash = new Hashtable();
foreach(string item in testForStrings)
{
bool isThere = (testString.IndexOf(item) > -1);
testHash.Add(item, isThere);
if(isThere)
{
testString = testString.Remove(testString.IndexOf(item),
item.Length);
}
}
return !testHash.ContainsValue(false);
}

Then I basically, to test, did the following:

string test = "The cow jumped and she jumped over the moon";
string[] items = "cow,jumped,jumped over".Split(',');

MessageBox.Show(TestString(items, test).ToString());

[gmiley]

You can use the following, and even with some modification you could
have it return a list of non-matches instead of bool.
public bool TestString(string[] testForStrings, string testString)
{
System.Collections.Hashtable testHash = new Hashtable();
foreach(string item in testForStrings)
{
bool isThere = (testString.IndexOf(item) > -1);
testHash.Add(item, isThere);
if(isThere)
{
testString = testString.Remove(testString.IndexOf(item),
item.Length);
}
}
return !testHash.ContainsValue(false);
}

Then I basically, to test, did the following:

string test = "The cow jumped and she jumped over the moon";
string[] items = "cow,jumped,jumped over".Split(',');

MessageBox.Show(TestString(items, test).ToString());

[Andrew Kirillov]

Ups, the next thing will not work in my sample. It is rather simple, just an
idea.

But, we can make a quick fix of the problem. Just search for longest needles
first.

--
With best regards,
Andrew

http://www.codeproject.com/script/pr...asp?id=1181072
"Spondishy" <sp*******@tiscali.co.uk> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...

Thanks for the quick response. To add more complexity what if the
string was

string source = "The cow jumped over the moon and then jumped higher";
string[] needles = new string[] {"cow", "jumped", "jumped over"};

This should pass because "jumped" and "jumped over" occur in the
original string.

[Andrew Kirillov]

Ups, the next thing will not work in my sample. It is rather simple, just an
idea.

But, we can make a quick fix of the problem. Just search for longest needles
first.

--
With best regards,
Andrew

http://www.codeproject.com/script/pr...asp?id=1181072
"Spondishy" <sp*******@tiscali.co.uk> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...

Thanks for the quick response. To add more complexity what if the
string was

string source = "The cow jumped over the moon and then jumped higher";
string[] needles = new string[] {"cow", "jumped", "jumped over"};

This should pass because "jumped" and "jumped over" occur in the
original string.