Search multiple strings in string

Question

In a given string, it is easy to search for the first occurrence of a substring like this:

int position = "01234".IndexOf ("23"); // returns 2

I want to search for the first occurrence of any of multiple possible strings:

var options = new [] {"77", "34", "12"};
int position = "01234".ImaginaryIndexOf (options); // should return 1

Such a function does not seem to exist in the .NET framework. Am I missing it?

Edit: To clarify, I am looking for a way that works well even for large inputs and unevenly distributed options. Imagine something similar to

var options = new [] {"x", "y"};
new String ('x', 1000*1000).IndexOf (options)

See: stackoverflow.com/questions/4075340/… var options = new[] { "77", "34", "12" }; int position = options.Select((value, index) => new { value, index = index + 1 }) .Where(pair => "01234".IndexOf(pair.value)>0) .Select(pair => pair.index) .FirstOrDefault(); — Y.L
– Y.L, Commented Jan 17, 2018 at 5:29
Please see edit to answer below - might supply an answer for the case of such a big string — Gilad Green
– Gilad Green, Commented Jan 17, 2018 at 12:16
Define "works well". String searching a million character string using a naive algorithm is still absurdly fast because large portions of the string get into the cache. Set a performance goal and see if the naive implementation meets the goal. It will be difficult to improve upon the naive algorithm. — Eric Lippert
– Eric Lippert, Commented Jan 17, 2018 at 15:25
I note that you can also be a little clever in a naive algorithm. For example, if a search has already found a hit at position 1000, then you can truncate every subsequent search at position 1000, since any hit after that will not be minimal. That could massively speed up the algorithm if you get lucky and find a hit early on. — Eric Lippert
– Eric Lippert, Commented Jan 17, 2018 at 19:40

Community · Accepted Answer · 2020-06-20 09:12:55Z

2

No built-in method that I'm aware of..

But in order to do so you can iterate all the options and for each calculate the IndexOf. Then retrieve the minimal that is not -1 (of "not found"):

int position = options.Select(o => "01234".IndexOf(o))
                      .OrderBy(i =>i).FirstOrDefault(i=> i != -1);

Or instead of sorting (which is O(nlogn)) find minimum (O(n)):

int position = options.Select(o => "01234".IndexOf(o))
                      .Where(i => i != -1).DefaultIfEmpty(-1).Min();

As for the edit what you can consider is constructing and array of suffix trees - the array contains m items where m is the distinct amount of first letters of your options words. As a general example:

if options is: "some", "word", "something", "other" then you'd construct:

    0        1        2...
 +-----------------------+
 |  s    |   w    |   o  |
 +- | ------ | ------ | -+
    o        o        t
    |        |        |
    m        r        h
    |        |        |
    e        d        e
   / \       |        |
  $   t      r        $
      |      |
      ...    $

Then you iterate your string and for each letter you check if it is in the array. If not continue to next. If it is then you can deepen in the nested tree and check next letter of string compared to next level in tree. If at the end of the main string you have not reached any of the $ then no item of options is in the text. Of course you can have the array as a HashSet<T> to improve the search of the first letter of a word.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jan 17, 2018 at 5:30

Gilad Green

37.3k7 gold badges67 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

mafu Over a year ago

This is what I'm doing right now. Sadly it has the drawback of reading the string multiple times.

Eric Lippert Over a year ago

@mafu: And why is that a problem?

Gilad Green Over a year ago

@mafu - how big is the "01234" string that it is a problem reading it several times? Anything that I can think of is still fine

Emre Kabaoglu · Accepted Answer · 2018-01-17 05:38:04Z

2

Maybe something like that;

var options = new[] { "77", "34", "12" };
var position = options.Select(x => "01234".IndexOf(x))
    .Where(x => x > -1).OrderBy(x => x).DefaultIfEmpty(-1)
    .FirstOrDefault();

You could define a string extension;

public static class StringExtensions
{
    public static int ImaginaryIndexOf(this string str,IEnumerable<string> options)
    {
        return options.Select(x => str.IndexOf(x))
            .Where(x => x > -1).OrderBy(x => x)
            .DefaultIfEmpty(-1).FirstOrDefault();
    }
}

Then;

var options = new[] { "77", "34", "12" };
"01234".ImaginaryIndexOf(options);

edited Jan 17, 2018 at 5:38

answered Jan 17, 2018 at 5:31

Emre Kabaoglu

13.2k4 gold badges27 silver badges48 bronze badges

Comments

Gowdham · Accepted Answer · 2018-01-17 05:39:09Z

0

Hi we can solve this by using for loop or by using regex.Try this following code I used for loop to find index of the first occurrence of a string.

var options = new[] { "77", "34", "12" };
        for (int i = 0; i < options.Length; i++)
        {
            //MessageBox.Show(options[i].ToString); 
            int p

var options = new[] { "77", "34", "12" };
for (int i = 0; i < options.Length; i++)
{

  int position = "770123473673412".IndexOf(options[i].ToString()); 
  MessageBox.Show(position.ToString());
}

answered Jan 17, 2018 at 5:39

Gowdham

1532 gold badges3 silver badges11 bronze badges

Comments

John Wu · Accepted Answer · 2018-01-17 06:09:30Z

0

Pretty easy with some LINQ. The tricky part is handling the -1... but if you understand unsigned and signed integers you can make this problem go away with a cast.

static class StringExtensions
{
    public static int ImaginaryIndexOf(this string input, IEnumerable<string> searchFor)
    {
        return (int)searchFor
            .Select
            (
                s => (uint)input.IndexOf(s) 
            )
            .Min();
    }
}

Try it out on DotNetFiddle.

answered Jan 17, 2018 at 6:09

John Wu

52.5k8 gold badges50 silver badges92 bronze badges

Comments

Serkan Arslan · Accepted Answer · 2018-01-17 06:51:49Z

0

As an alternative solution, you can use Regex

string input = "01234";
var rgex = new System.Text.RegularExpressions.Regex("(77|34|12)");
var match = rgex.Match(input);
int position = match.Success ? match.Index : -1;

edited Jan 17, 2018 at 6:51

answered Jan 17, 2018 at 6:31

Serkan Arslan

13.4k4 gold badges33 silver badges46 bronze badges

Comments

Gowdham · Accepted Answer · 2018-01-17 05:44:16Z

-3

Hi we can solve this by using for loop or by using regex.Try this following code I used for loop to find index of the first occurrence of a string.

var options = new[] { "77", "34", "12" };
for (int i = 0; i < options.Length; i++)
{

  int position = "770123473673412".IndexOf(options[i].ToString()); 
  MessageBox.Show(position.ToString());
}

answered Jan 17, 2018 at 5:44

Gowdham

1532 gold badges3 silver badges11 bronze badges

1 Comment

Gilad Green Over a year ago

Do not post same answer twice

Collectives™ on Stack Overflow

Search multiple strings in string

6 Answers 6

3 Comments

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related