Ich dachte, ich würde meine Erweiterungsmethode in den Ring werfen (siehe Kommentare für weitere Informationen). Ich habe keine formalen Tests durchgeführt, aber ich denke, dass es für die meisten Szenarien sehr schnell sein muss.
EDIT: OK - diese SO-Frage brachte mich dazu, mich zu fragen, wie die Leistung unserer aktuellen Implementierung im Vergleich zu einigen der hier vorgestellten Lösungen abschneiden würde. Ich beschloss, einen kleinen Leistungsvergleich durchzuführen, und stellte fest, dass unsere Lösung sehr gut mit der Leistung der Lösung von Richard Watson bis zu einer aggressiven Suche mit großen Zeichenfolgen (100 Kb +), großen Teilzeichenfolgen (32 Kb +) und vielen eingebetteten Wiederholungen (10K +). An diesem Punkt war unsere Lösung etwa 2- bis 4-mal langsamer. Angesichts dessen und der Tatsache, dass uns die von Richard Watson vorgestellte Lösung sehr gut gefällt, haben wir unsere Lösung entsprechend umgestaltet. Ich wollte dies nur allen zur Verfügung stellen, die davon profitieren könnten.
Unsere ursprüngliche Lösung:
/// <summary>
/// Counts the number of occurrences of the specified substring within
/// the current string.
/// </summary>
/// <param name="s">The current string.</param>
/// <param name="substring">The substring we are searching for.</param>
/// <param name="aggressiveSearch">Indicates whether or not the algorithm
/// should be aggressive in its search behavior (see Remarks). Default
/// behavior is non-aggressive.</param>
/// <remarks>This algorithm has two search modes - aggressive and
/// non-aggressive. When in aggressive search mode (aggressiveSearch =
/// true), the algorithm will try to match at every possible starting
/// character index within the string. When false, all subsequent
/// character indexes within a substring match will not be evaluated.
/// For example, if the string was 'abbbc' and we were searching for
/// the substring 'bb', then aggressive search would find 2 matches
/// with starting indexes of 1 and 2. Non aggressive search would find
/// just 1 match with starting index at 1. After the match was made,
/// the non aggressive search would attempt to make it's next match
/// starting at index 3 instead of 2.</remarks>
/// <returns>The count of occurrences of the substring within the string.</returns>
public static int CountOccurrences(this string s, string substring,
bool aggressiveSearch = false)
{
// if s or substring is null or empty, substring cannot be found in s
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(substring))
return 0;
// if the length of substring is greater than the length of s,
// substring cannot be found in s
if (substring.Length > s.Length)
return 0;
var sChars = s.ToCharArray();
var substringChars = substring.ToCharArray();
var count = 0;
var sCharsIndex = 0;
// substring cannot start in s beyond following index
var lastStartIndex = sChars.Length - substringChars.Length;
while (sCharsIndex <= lastStartIndex)
{
if (sChars[sCharsIndex] == substringChars[0])
{
// potential match checking
var match = true;
var offset = 1;
while (offset < substringChars.Length)
{
if (sChars[sCharsIndex + offset] != substringChars[offset])
{
match = false;
break;
}
offset++;
}
if (match)
{
count++;
// if aggressive, just advance to next char in s, otherwise,
// skip past the match just found in s
sCharsIndex += aggressiveSearch ? 1 : substringChars.Length;
}
else
{
// no match found, just move to next char in s
sCharsIndex++;
}
}
else
{
// no match at current index, move along
sCharsIndex++;
}
}
return count;
}
Und hier ist unsere überarbeitete Lösung:
/// <summary>
/// Counts the number of occurrences of the specified substring within
/// the current string.
/// </summary>
/// <param name="s">The current string.</param>
/// <param name="substring">The substring we are searching for.</param>
/// <param name="aggressiveSearch">Indicates whether or not the algorithm
/// should be aggressive in its search behavior (see Remarks). Default
/// behavior is non-aggressive.</param>
/// <remarks>This algorithm has two search modes - aggressive and
/// non-aggressive. When in aggressive search mode (aggressiveSearch =
/// true), the algorithm will try to match at every possible starting
/// character index within the string. When false, all subsequent
/// character indexes within a substring match will not be evaluated.
/// For example, if the string was 'abbbc' and we were searching for
/// the substring 'bb', then aggressive search would find 2 matches
/// with starting indexes of 1 and 2. Non aggressive search would find
/// just 1 match with starting index at 1. After the match was made,
/// the non aggressive search would attempt to make it's next match
/// starting at index 3 instead of 2.</remarks>
/// <returns>The count of occurrences of the substring within the string.</returns>
public static int CountOccurrences(this string s, string substring,
bool aggressiveSearch = false)
{
// if s or substring is null or empty, substring cannot be found in s
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(substring))
return 0;
// if the length of substring is greater than the length of s,
// substring cannot be found in s
if (substring.Length > s.Length)
return 0;
int count = 0, n = 0;
while ((n = s.IndexOf(substring, n, StringComparison.InvariantCulture)) != -1)
{
if (aggressiveSearch)
n++;
else
n += substring.Length;
count++;
}
return count;
}
