Search one List<t> for a sub List<t>

[Andrew Robinson]

I have two List<t>. I need to search ListA to see if it contains ListB

So:

ListA { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Searching ListA with { 4, 5, 6 } would return true and an index of 3.
Searching ListA with { 4, 6, 5 } would return false and or an index of -1.

Hope my pseudo coding is clear?

Is there any easy way of doing this with generic lists? I am looking at
lists of strings for now.

Thanks,

 

[KJ]

This is an interesting post, and I wonder if anyone has implemented a
Set class yet using generics (and would like to share it).

 

[Michael Bray]

This is an interesting post, and I wonder if anyone has implemented a
Set class yet using generics (and would like to share it).

Although it doesn't directly affect your question, in detail, he couldn't
use a set class because he is dependent on order, which is contrary to set
theory.

-mdb

 

[Andrew Robinson]

ok, did a bruit force type thing. would appreciate any comments on the code.
Seems to work:

using System;

using System.Collections.Generic;

using System.Text;



class ListSearch<T>

{

public ListSearch()

{

}



public int IndexOf(List<T> list, List<T> subList)

{

return IndexOf(list, subList, 0);

}



public int IndexOf(List<T> list, List<T> subList, int start)

{

T s = subList[0];



int i = list.FindIndex(start, delegate(T t) { return
t.Equals(s); });



if (i < 0)

{

// found no initial match

return -1;

}



for (int j = 1; j < subList.Count; j++)

{

if (!list[j + i].Equals(subList[j]))

{

// got here because we found a non equal value.

// if there are more elements in the list, start over at the
next element



if (j + i < list.Count)

{

return IndexOf(list, subList, i + 1);

}

else

{

return -1;

}

}

}



return i;

}

}



List<int> list = new List<int>();

List<int> subList = new List<int>();



list.Add(1); // 0

list.Add(2); // 1

list.Add(3); // 2

list.Add(4); // 3

list.Add(4); // 4

list.Add(5); // 5



subList.Add(4);

subList.Add(5);



ListSearch<int> listSearch = new ListSearch<int>();



int i = listSearch.IndexOf(list, subList);


returns 4 which is correct.

 

[Luke Zhang [MSFT]]

How about this:

class SearchableList<T> : List<T>
{


public int FindSubList(SearchableList<T> sublist, int start)
{


for (int i = start; i <= this.Count-sublist.Count ; i++)
{
int j;
for (j = 0; j < sublist.Count; j++)
if (!this[i+j].Equals(sublist[j]) ) break;

if (j==sublist.Count )
return i ;
}

return -1;
}
}


Luke

 

[Andrew Robinson]

Luke,

Your version is cleaner but think they perform the same. I modified it a bit
further.

Thanks!

public class ListSearch<T>
{
public static int IndexOf(List<T> list, List<T> sublist)
{
return IndexOf(0, list, sublist);
}

public static int IndexOf(int start, List<T> list, List<T> sublist)
{
for (int i = start; i <= list.Count - sublist.Count; i++)
{
int j = 0;
while (j < sublist.Count)
{
if (!list[i + j].Equals(sublist[j++])) break;
}
if (j == sublist.Count) return i;
}

return -1;
}
}

 

[Andrew Robinson]

Slight bug. Fixed:

public static class ListSearch<T>
{
public static int IndexOf(List<T> list, List<T> sublist)
{
return IndexOf(0, list, sublist);
}

public static int IndexOf(int start, List<T> list, List<T> sublist)
{
for (int i = start; i <= list.Count - sublist.Count; i++)
{
int j = 0;
while (j < sublist.Count)
{
if (!list[i + j].Equals(sublist[j])) break;
if (j < sublist.Count) j++;
}

if (j == sublist.Count) return i;
}

return -1;
}
}

 

[Luke Zhang [MSFT]]

Looks great!


Luke