logo标签列表

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

c#.netasp.netstring
94

我有一个大字符串需要解析，我需要找到所有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 = 大字符串

还有更好的想法吗？

16个回答
166

这是一个用于扩展的示例方法：

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;
    }
}
9
为什么不使用IEnumerable<int>和yield return index，而是使用索引列表呢？ - m0sa
2
@m0sa：好观点。又加了一个版本，只是为了好玩。 - Matti Virkkunen
2
@PedroC88：使用 yield 会使代码变得“懒惰”。它不会在方法内部将所有索引收集到内存列表中。这对性能的实际影响取决于许多因素。 - Matti Virkkunen
14
注意！由于添加了 value.Length，您可能会错过嵌套匹配！例如："This is a NestedNestedNested match test!"，对于 "NestedNested" 的匹配只会找到一个索引而不是嵌套的一个。为了解决这个问题，在循环中只需将 +=1 添加进去，而不是 +=value.Length。 - Christoph Meißner
2
你的解决方案不正确！对于在“aaa”中查找“aa”，输出应该是[0, 1]，但你的算法返回了[0]。 - Mojtaba Khooryani
显示剩余9条评论
25

为什么不使用内置的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以用于重复使用的情况。

这个无法编译。 - Anshul
indexes是什么？它在任何地方都没有被定义过。 - Saggio
我的错，那是一个残留物。请删除那一行。 - csaam
2
请注意，此方法与被接受的答案具有相同的缺陷。如果您的源字符串为“ccc”，模式为“cc”，则它将仅返回一个匹配项。 - user280498
2
@user280498 这并不一定是一个“缺陷”，这取决于使用场景... - Mr. Squirrel.Downy
18

使用LINQ

public static IEnumerable<int> IndexOfAll(this string sourceString, string subString)
{
    return Regex.Matches(sourceString, subString).Cast<Match>().Select(m => m.Index);
}
4
你忘记转义子字符串了。 - csaam
这种解决方案比被接受的方案更可取，因为它具有更低的圈复杂度。 - Denny Jacob
2
似乎对于输入 "aaa" 和 "aa"，并不能正常工作。 - Kylo Ren
当你在“aaa”中匹配“aa”时，预期的行为是剩下的是“xxa”，它不匹配“aa”。 - ehosca
啊哈，下一个注释就是这样——我的文件名恰好以AA开头。 :)我得到了一个字符串，将被解析成电子邮件的正文。有些原因我不能修改返回消息的代码。我必须解析返回的消息。示例名称为AA.AAOAKSINF02A.DEV.DAT。有一定数量。我必须找到所有文件名并验证正确的计数存在，然后考虑任何未发生的情况。好的，怎么做呢？我需要找到每个AA和它的下一个.DEV实例。在它们之间是文件名和日期。 - user1585204
10

更加精炼的版本+支持大小写忽略:

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();
}
6

使用KMP算法，可以在O（N + M）的时间复杂度内高效完成。其中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
        }
    }
与将搜索起始索引设置为每次迭代上一个匹配的末尾相比，这种实现的性能如何？ - caesay
比较IndexOf和AllIndicesOf是不正确的，因为它们的输出不同。在每次迭代中使用IndexOf方法会极大地增加时间复杂度到O(N^2 M)，而最优复杂度是O(N+M)。KMP与朴素方法不同，它使用预计算数组(LPS)来避免从头开始搜索。建议您阅读KMP算法。维基百科的“背景”部分的最后一段解释了它如何以O(N)的时间复杂度工作。 - Mojtaba Khooryani
C# 中的其他字符串搜索算法？ - Kiquenet
1
我不明白为什么更多的人没有接受这个答案。它在长输入字符串和长搜索字符串上的表现更好。虽然阅读起来更复杂，但将其视为黑匣子并将其用作解决具有长输入字符串的问题的首选方法是正确的选择。 - drdwilcox
1
因为这个答案是在经过验证的答案发布10年后发布的，所以@drdwilcox。 - Mojtaba Khooryani
3

我注意到至少有两个提出的解决方案没有处理重叠的搜索结果。我没有检查标记为绿色勾号的那一个。这里有一个可以处理重叠搜索结果的解决方案：

    public static List<int> GetPositions(this string source, string searchString)
    {
        List<int> ret = new List<int>();
        int len = searchString.Length;
        int start = -1;
        while (true)
        {
            start = source.IndexOf(searchString, start +1);
            if (start == -1)
            {
                break;
            }
            else
            {
                ret.Add(start);
            }
        }
        return ret;
    }
2
public List<int> GetPositions(string source, string searchString)
{
    List<int> ret = new List<int>();
    int len = searchString.Length;
    int start = -len;
    while (true)
    {
        start = source.IndexOf(searchString, start + len);
        if (start == -1)
        {
            break;
        }
        else
        {
            ret.Add(start);
        }
    }
    return ret;
}

这样调用：

List<int> list = GetPositions("bob is a chowder head bob bob sldfjl", "bob");
// list will contain 0, 22, 26
将以下文本从英语翻译为中文：添加此检查，您就可以继续前进： 如果 (searchString == null || searchString == String.Empty) { ret.Add(-1); return ret; }; - MC9000
2

没有使用正则表达式，而是使用字符串比较类型的方法：

string search = "123aa456AA789bb9991AACAA";
string pattern = "AA";
Enumerable.Range(0, search.Length)
   .Select(index => { return new { Index = index, Length = (index + pattern.Length) > search.Length ? search.Length - index : pattern.Length }; })
   .Where(searchbit => searchbit.Length == pattern.Length && pattern.Equals(search.Substring(searchbit.Index, searchbit.Length),StringComparison.OrdinalIgnoreCase))
   .Select(searchbit => searchbit.Index)

这将返回{3,8,19,22}。空模式将匹配所有位置。

对于多个模式：

string search = "123aa456AA789bb9991AACAA";
string[] patterns = new string[] { "aa", "99" };
patterns.SelectMany(pattern => Enumerable.Range(0, search.Length)
   .Select(index => { return new { Index = index, Length = (index + pattern.Length) > search.Length ? search.Length - index : pattern.Length }; })
   .Where(searchbit => searchbit.Length == pattern.Length && pattern.Equals(search.Substring(searchbit.Index, searchbit.Length), StringComparison.OrdinalIgnoreCase))
   .Select(searchbit => searchbit.Index))

这将返回{3, 8, 19, 22, 15, 16}。

哈哈，看到我上面的评论了吗？我做了那么多工作，只是为了读几行更多的文字，才发现“不使用正则表达式，使用字符串比较类型：”。非常感谢您的帮助，很容易忽略只有1个赞的答案。很高兴看到这个。 - user1585204
var x = Enumerable.Range(0, search.Length - pattern.Length + 1).Where(index => pattern.Equals(search.Substring(index, pattern.Length))); 是你第一个答案的简化版本。 - undefined
1

嗨，@Matti Virkkunen 给出了很好的答案

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);
        index--;
    }
}

但这包括像AOOAOOA这样的测试用例，其中子字符串为AOOA和AOOA。
输出0和3。
1

@csam 的理论是正确的，尽管他的代码无法编译并需要重构。

public static IEnumerable<int> IndexOfAll(this string sourceString, string matchString)
{
    matchString = Regex.Escape(matchString);
    return from Match match in Regex.Matches(sourceString, matchString) select match.Index;
}
如果他的代码有误，你可以编辑他的帖子进行更正。 - caesay
1
我没有注意到那个。我必须承认我有些不愿意去做那件事，因为我担心自己可能是错的，尽管我并不认为我错了。 - arame3333
在处理大字符串时使用正则表达式不是一个好主意。这种方法会消耗大量内存。 - Marek Woźniak
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接