在C#中查找更大字符串中子字符串的所有位置

Question

我有一个需要解析的大字符串,我需要查找所有实例extract"(me,i-have lots. of]punctuation,并将每个的索引存储到列表中.

所以说这条字符串位于较大字符串的开头和中间,它们都会被找到,并且它们的索引会被添加到字符串中List.而List将包含0与其他指数不管它是.

我一直在玩弄和string.IndexOf做几乎就是我正在寻找的,我已经写了一些代码-但它不工作,我一直无法弄清楚到底什么是错的:

List<int> inst = new List<int>();
int index = 0;
while (index < source.LastIndexOf("extract\"(me,i-have lots. of]punctuation", 0) + 39)
{
    int src = source.IndexOf("extract\"(me,i-have lots. of]punctuation", index);
    inst.Add(src);
    index = src + 40;
}

• inst =清单
• source =大字符串

有更好的想法吗？

Answer 1

这是一个示例扩展方法:

public static List<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    List<int> indexes = new List<int>();
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            return indexes;
        indexes.Add(index);
    }
}

如果将其放入静态类并导入命名空间using,则它在任何字符串上显示为方法,您可以这样做:

List<int> indexes = "fooStringfooBar".AllIndexesOf("foo");

有关扩展方法的更多信息,请访问http://msdn.microsoft.com/en-us/library/bb383977.aspx

使用迭代器也一样:

public static IEnumerable<int> AllIndexesOf(this string str, string value) {
    if (String.IsNullOrEmpty(value))
        throw new ArgumentException("the string to find may not be empty", "value");
    for (int index = 0;; index += value.Length) {
        index = str.IndexOf(value, index);
        if (index == -1)
            break;
        yield return index;
    }
}

Answer 2

为什么不使用内置的RegEx类:

public static IEnumerable<int> GetAllIndexes(this string source, string matchString)
{
   matchString = Regex.Escape(matchString);
   foreach (Match match in Regex.Matches(source, matchString))
   {
      yield return match.Index;
   }
}

如果你确实需要重用表达式,那么编译它并在某处缓存它.将matchString参数更改为另一个重载中的Regex matchExpression以用于重用案例.

Answer 3

使用LINQ

public static IEnumerable<int> IndexOfAll(this string sourceString, string subString)
{
    return Regex.Matches(sourceString, subString).Cast<Match>().Select(m => m.Index);
}

Answer 4

可以使用 O(N + M) 中的KMP算法以有效的时间复杂度完成，其中 N 是 的长度text，M 是 的长度pattern。

这是实现和使用：

static class StringExtensions
{
    public static IEnumerable<int> AllIndicesOf(this string text, string pattern)
    {
        if (string.IsNullOrEmpty(pattern))
        {
            throw new ArgumentNullException(nameof(pattern));
        }
        return Kmp(text, pattern);
    }

    private static IEnumerable<int> Kmp(string text, string pattern)
    {
        int M = pattern.Length;
        int N = text.Length;

        int[] lps = LongestPrefixSuffix(pattern);
        int i = 0, j = 0; 

        while (i < N)
        {
            if (pattern[j] == text[i])
            {
                j++;
                i++;
            }
            if (j == M)
            {
                yield return i - j;
                j = lps[j - 1];
            }

            else if (i < N && pattern[j] != text[i])
            {
                if (j != 0)
                {
                    j = lps[j - 1];
                }
                else
                {
                    i++;
                }
            }
        }
    }

    private static int[] LongestPrefixSuffix(string pattern)
    {
        int[] lps = new int[pattern.Length];
        int length = 0;
        int i = 1;

        while (i < pattern.Length)
        {
            if (pattern[i] == pattern[length])
            {
                length++;
                lps[i] = length;
                i++;
            }
            else
            {
                if (length != 0)
                {
                    length = lps[length - 1];
                }
                else
                {
                    lps[i] = length;
                    i++;
                }
            }
        }
        return lps;
    }

这是如何使用它的示例：

static void Main(string[] args)
    {
        string text = "this is a test";
        string pattern = "is";
        foreach (var index in text.AllIndicesOf(pattern))
        {
            Console.WriteLine(index); // 2 5
        }
    }

Answer 5

抛光版+案例忽略支持:

public static int[] AllIndexesOf(string str, string substr, bool ignoreCase = false)
{
    if (string.IsNullOrWhiteSpace(str) ||
        string.IsNullOrWhiteSpace(substr))
    {
        throw new ArgumentException("String or substring is not specified.");
    }

    var indexes = new List<int>();
    int index = 0;

    while ((index = str.IndexOf(substr, index, ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal)) != -1)
    {
        indexes.Add(index++);
    }

    return indexes.ToArray();
}