Example: there is the first line with the text "AByrjujABw qr" , and there is the second line with the text "AB" . Accordingly, the second met in the first 2 times. How to calculate this in C #? Is there a function ready, or invent their own?

  • In my opinion it would be best through regular season - Vitaly Shebanits
  • Search for a substring . - Alexander Petrov
  • Linq-option (so far without it?): string a = "AByrjujABw qr"; string b = "AB"; int c = a.Select((_, i) => a.Skip(i).Take(b.Length)).Count(s => s.SequenceEqual(b)); Console.WriteLine(c); string a = "AByrjujABw qr"; string b = "AB"; int c = a.Select((_, i) => a.Skip(i).Take(b.Length)).Count(s => s.SequenceEqual(b)); Console.WriteLine(c); - Andrey NOP

5 answers 5

Give me too:

 string a = "AByrjujABw qr"; string b = "AB"; int n = (a.Length - a.Replace(b, "").Length) / b.Length;
  • I would not even think about such a simple option, definitely plus :) - tym32167
  • @ tym32167 I saw the answer about this trinity, my hands immediately itched). - Igor
  • Beautiful decision. However, Replace creates a new line. As a result, the memory consumption may be inefficient. - Alexander Petrov

Option with IndexOf :

 string a = "AByrjujABw qr"; string b = "AB"; int c = 0, i = -1; while ((i = a.IndexOf(b, i + 1)) > -1) ++c; Console.WriteLine(c);

If you want to exclude intersections of occurrences ( ABA in ABABA find once, not two), you can rewrite it like this:

 int c = 0, i = -b.Length; while ((i = a.IndexOf(b, i + b.Length)) > -1) ++c;
  • A good option: one pass, optimal search, no memory allocation. The only thing that can occur is ambiguity with overlapping fragments, mentioned by @iksuy. i + b.Length ? - Igor
  • @Igor, thanks, added! - Andrey NOP

The problem can be solved using the Knut-Morris-Pratt algorithm.

Suppose we have the required substring substring , the initial string str , and the delimiter character such that it is not included in the substring or in str . Then we can make a string like: substring + разделитель + str and walk through it with the prefix function :

I bring the code in Java , I think that it will not be difficult for you to rewrite it in C#

 public static void main(String args []) { String str = "AByrjujABw qr"; String substring = "AB"; String full = substring + "#" + str; int[] prefix = prefix(full.toCharArray()); System.out.println(Arrays.toString(prefix)); } private static int[] prefix(char[] s){ int n = s.length; int[] pi = new int[n]; for (int i = 1; i < n; ++i) { int j = pi[i-1]; while (j > 0 && s[i] != s[j]) j = pi[j-1]; if (s[i] == s[j]) ++j; pi[i] = j; } return pi; }

After passing the prefix function, you need to go through the prefix array and count the number of numbers equal to the length of your search string, this will be the answer.

The result of the prefix function:

[0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0]

the length of the required substring is 2, the number 2 in the prefix array occurs 2 times.

Note that the algorithm will produce a result when the substrings are crossed, for example, having the string:

 str = "ABAxxABABAyy"; substring = "ABA";

the result will be equal to 3, since ABA occurs in fact 3 times, 2 of which intersect (substring ABABA )

  • ILC is great. But this: substring + "#" + str is not great. I have already burned so much on the extinction of memory when working with strings in dotnet ... - Alexander Petrov

Training:

 var str = "AByrjujABw qr"; var separator = "AB";

Option 1 (use Split() ):

 var splitResult = str.Split(new [] {separator}, StringSplitOptions.None).Length-1;

Option 2 (use Regex ):

 var regexResult = Regex.Matches(str, separator).Count; 
     string a = "AByrjujABw qr"; string b = "AB"; int c = 0, i = -1; while ((i = a.IndexOf(b, i + 1)) > -1) ++c;
    • 2
      What is the difference from my version ? - Andrey NOP