Найти Сколько раз анаграмма содержится в строке - asp. net c#

Question

Мне нужно выяснить, сколько раз анаграммы содержатся в строке, как в этом примере: (анаграммы и сама строка)

Вход 1 (строка) = thegodsanddogsededogged

Вход 2 (String) = собака

Выход (int) = 3 выход будет 3 из-за них - ( бог песок собака Swere собака ged)

Пока мне удалось проверить, сколько раз слово "собака" содержится в строке:

        public ActionResult FindAnagram (string word1, string word2)
        {
            int ?count = Regex.Matches(word1, word2).Count;

            return View(count);
        }

Это работает, чтобы проверить, сколько раз слово содержится в но я все еще получаю сообщение об ошибке: не могу преобразовать ноль в 'int', потому что это тип значения, не равный нулю.

Так что мне нужно проверить, сколько раз input 2 и анаграммы input 2 ( собака, бог, d go, огд и др. c) содержатся в input 1? (в данном случае это 3 раза - бог песок собака Swere собака гед)

спасибо

Answer 1

Я хотел опубликовать вариант, который будет более читабельным за счет некоторой производительности во время выполнения. Ответ Антона, вероятно, более производительный, но ИМХО менее читабельный, чем мог бы быть.

Хорошая особенность анаграмм заключается в том, что вы знаете их точную длину, и вы можете легко определить все возможные местоположения анаграмм. Для трехбуквенной анаграммы в стоге сена из 100 букв вы знаете, что существует 98 возможных мест:

• 0..2
• 1..3
• 2 ..4
• ...
• 96..98
• 97..99

Эти индексы могут быть сгенерированы довольно легко:

var amountOfPossibleAnagramLocations = haystack.Length - needle.Length + 1;

var substringIndexes = Enumerable.Range(0, amountOfPossibleAnagramLocations);

На этом этапе вы просто берете каждую указанную подстроку и проверяете, является ли она анаграммой.

var anagramLength = needle.Length;
int count = 0;

foreach(var index in substringIndexes)
{
    var substring = haystack.Substring(index, anagramLength);

    if(substring.IsAnagramOf(needle))
        count++;
}

Обратите внимание, что многое из этого может быть сведено в одну цепочку LINQ:

var amountOfPossibleAnagramLocations = haystack.Length - needle.Length + 1;
var anagramLength = needle.Length;

var anagramCount = Enumerable
                      .Range(0, amountOfPossibleAnagramLocations)
                      .Select(x => haystack.Substring(x, anagramLength))
                      .Count(substring => substring.IsAnagramOf(needle));

Будет ли он более читабельным или нет, зависит от того, насколько вам удобно с LINQ. Я лично предпочитаю это (конечно, до разумного размера).

---

Чтобы проверить анаграмму, просто сортируйте символы и проверяйте равенство. Я использовал метод расширения для бонуса читабельности:

public static bool IsAnagramOf(this string word1, string word2)
{
    var word1Sorted = String.Concat(word1.OrderBy(c => c));
    var word2Sorted = String.Concat(word2.OrderBy(c => c));

    return word1Sorted == word2Sorted;
}

Я пропустил такие вещи, как нечувствительность к регистру или игнорирование пробелов для краткости.

Answer 2

Лучше не пытаться использовать Regex, но написать свою собственную логику c.

Вы можете использовать словарь с ключом char - буквой слова и значением int - количество вхождений букв. И построить такой словарь для слова.

Анаграммы будут иметь аналогичные словари, так что вы можете создать временный словарь для каждой временной строки, построенной с использованием метода Windowing поверх вашей str, и сравнить ее со словарем, созданным для вашего слова.

Здесь мой код:

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {

            var str = "thegodsanddogsweredogged";
            var word = "dog";
            Console.WriteLine("Word: " + word);
            Console.WriteLine("Str: " + str);
            Console.WriteLine();

            var count = CountAnagrams(str, word);
            Console.WriteLine("Count: " + count);

            Console.ReadKey();
        }


        private static int CountAnagrams(string str, string word) {
            var charDict = BuildCharDict(word);
            int count = 0;

            for (int i = 0; i < str.Length - word.Length + 1; i++) {
                string tmp = "";
                for (int j = i; j < str.Length; j++) {
                    tmp += str[j];
                    if (tmp.Length == word.Length)
                        break;
                }

                var tmpCharDict = BuildCharDict(tmp);

                if (CharDictsEqual(charDict, tmpCharDict)) {
                    count++;
                    Console.WriteLine("Anagram: " + tmp);
                    Console.WriteLine("Index: " + i);
                    Console.WriteLine();
                }

            }


            return count;
        }

        private static Dictionary<char, int> BuildCharDict(string word) {
            var charDict = new Dictionary<char, int>();
            foreach (var ch in word)
            {
                if (charDict.ContainsKey(ch))
                {
                    charDict[ch] += 1;
                }
                else
                {
                    charDict[ch] = 1;
                }
            }

            return charDict;
        }

        private static bool CharDictsEqual(Dictionary<char, int> dict1, Dictionary<char, int> dict2) 
        {
            if (dict1.Count != dict2.Count)
                return false;

            foreach (var kv in dict1) {
                if (!dict2.TryGetValue(kv.Key, out var val) || val != kv.Value)
                {
                    return false;
                }
            }

            return true;
        } 
    }
}

Возможно, есть лучшее решение, но мое работает.

PS О вашей ошибке. Вам следует изменить int? на int, потому что ваш View может ожидать, что не обнуляется int type