7

Пример: есть первая строка с текстом "AByrjujABw qr", и есть вторая с текстом "AB". Соотвественно, вторая встретилась в первой 2 раза. Как такое посчитать на C#? Есть ли функция готовая, или свою выдумывать?

3
  • По моему лучше всего будет через регулярки 23 окт 2018 в 16:06
  • Поиск подстроки. 23 окт 2018 в 18:13
  • Linq-вариант (куда уж без него?): 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); 24 окт 2018 в 5:51

6 ответов 6

18

Дайте и мне:

string a = "AByrjujABw qr";
string b = "AB";
int n = (a.Length - a.Replace(b, "").Length) / b.Length;
2
  • Я бы даже не подумал про такой простой вариант, однозначно плюсую :)
    – tym32167
    23 окт 2018 в 15:57
  • Красивое решение. Однако, Replace создаёт новую строку. В итоге по расходу памяти может быть неэффективно. 23 окт 2018 в 17:50
7

Задачу можно решить с помощью алгоритма Кнута-Морриса-Пратта

Пусть у нас есть искомая подстрока substring, исходная строка str, и символ-разделитель, такой что он не входит ни в substring, ни в str. Тогда мы можем составить строку вида: substring + разделитель + str и пройтись по ней префикс-функцией:

Привожу код на Java, думаю что вам не составит труда переписать его на 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;
}

После прохода префикс-функцией вам нужно пройтись по массиву prefix и посчитать количество чисел, равных длине вашей искомой подстроки, это и будет ответом.

Результат выполнения префикс-функции:

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

длина искомой подстроки - 2, число 2 в префиксном массиве встречается 2 раза.

Обратите внимание, что алгоритм даст результат при пересечении подстрок, например имея строки:

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

результат будет равен 3, так как ABA встречается фактически 3 раза, 2 из которых пересекаются (подстрока ABABA)

1
  • КМП - это здорово. Но вот это: substring + "#" + str - не здорово. Я уже столько обжигался на выжирании памяти при работе со строками в дотнете... 23 окт 2018 в 17:52
7

Вариант с 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);

Если вы хотите исключать пересечения вхождений (ABA в ABABA находить один раз, а не два), то можно переписать так:

int c = 0, i = -b.Length;
while ((i = a.IndexOf(b, i + b.Length)) > -1) ++c;
2
  • Хороший вариант: один проход, оптимальный поиск, нет распределения памяти. Единственное, может возникнуть неоднозначность с наложением фрагментов, упомянутая @iksuy. i + b.Length?
    – user176262
    24 окт 2018 в 5:32
  • @Igor, спасибо, добавил! 26 окт 2018 в 5:58
6

Подготовка:

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

Вариант 1 (используем Split()):

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

Вариант 2 (используем Regex):

var regexResult = Regex.Matches(str, separator).Count;
0
string a = "AByrjujABw qr";
string b = "AB";
int c = 0, i = -1;
while ((i = a.IndexOf(b, i + 1)) > -1) ++c;
1
0

Если нужно быстро, чтобы недолго париться, то можно через лямбда-функцию Count():

string s = "100101000010010";
string sub = "10";
int result = s.Replace(sub,"*").Count(x => x == '*');
//result = 5
//Вместо звездочки можно использовать любой другой символ UTF, 
//например зажать alt и нажать 1 для "☺"

Использовать, если вас удовлетворяет Replace().

Новый участник
AceOfIce — новый участник сайта. Будьте снисходительны, задавая уточняющие вопросы, комментируя и отвечая. Почитайте про нормы поведения.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.