Efficient way to determine if any obscene words are contained in a randomly generated code in .NET

Question

We have an application that generates random base 35 numbers [0-9A-Z] excluding the letter O. I am looking for a solution to find codes that contain any obscene english words without having to search through a list of 10,000 entries per each generated code. Tens of Thousands of codes are generated a second, search time for these huge lists of obscene words will either crush our servers or require a lot more instances to support any meaningful decrease in performance.

Due to the nature of this code generator, obscenity checks need to be efficient and high performance.

Please note that omitting vowels is not an option as base 35 is required and mixed casing is not an option. The problem here is more than just an algorithm, efficient string matching and searching is only a small portion of the problem.

A portion of this would entail taking a list of strings and finding the commonly duplicated substrings of a given length (3 for instance) and omitting all words in a list containing those common substrings to generate an optimized list. This would help is abbreviating the lengthy obscene filter lists in the wild to solve the need here.

Answer 1

Considering that the traditional chain of contains doesn't perform well enough in your scenario, a Trie data structure might be a good start. The Trie traversal time is quite fast. It's O(m) where m is the length of a search string. In other words, it's almost constant time if the Trie is well structured.

Here is an example in C#

Answer 2

Building off of @yazanpro's trie suggestion, it was possible to build a solution which not only can search the words but also stop additional searches where ABC needs to be omitted so there is no need to check for ABCFACE, ABCHOLE, ABCHEAD...

The logic inside the tree hydration is currently in place to format from an non-optimized list of words to construct an optimized list of words 10 to a line. Copy the output and paste back in as the new WORDS list.

The value storage for each tree node, this could be optimized to not require storage of the word. However, storing the word makes this easier to debug change IsObscene to a settable property instead of using word:

    public class ObsceneValue
{
    public bool IsObscene
    {
        get { return Word != null; }
    }

    public string Word { get; set; }
    public char Character { get; set; }

    public ObsceneValue(char character, string fullWord = null)
    {
        Character = character;
        Word = fullWord;
    }
}

The node to represent the tree structure:

    public class ObsceneNode
{
    public ObsceneNode(ObsceneValue value)
    {
        Value = value;
        Children = new Dictionary<char, ObsceneNode>();
    }

    public ObsceneValue Value { get; set; }
    public Dictionary<char, ObsceneNode> Children { get; set; }

    public bool HasChild(char character)
    {
        return Children.ContainsKey(character);
    }

    public ObsceneNode SafeAddChild(ObsceneValue value)
    {
        if (HasChild(value.Character))
        {
            return GetChild(value.Character);
        }

        var node = new ObsceneNode(value);
        Children.Add(value.Character, node);
        return node;
    }

    public ObsceneNode GetChild(char character)
    {
        if (HasChild(character))
        {
            return Children[character];
        }

        return null;
    }
}

The actual obscenity filter, which has debug logic to omit duplicates found in nearly every list of obscene words on the internet which would require redundant checks or in this case deeper than needed trees:

        public static string[] WORDS = new[]
    {
        "ANY","LIST","OF","WORDS"
    };

    private static ObsceneNode _root;

    static SmutBlocker()
    {
        //abbreviatedList can be omitted once an optimized list of
        //terms is set to WORDS.
        var abbreviatedList = new List<string>();
        _root = new ObsceneNode(new ObsceneValue(default(char), null));
        var iter = _root;
        foreach (var word in WORDS)
        {
            for(var i = 0; i < word.Length; i++)
            {
                if (iter.Value.IsObscene)
                    break;

                var isObscene = (word.Length - 1) == i;
                iter = iter.SafeAddChild(new ObsceneValue(word[i], isObscene ? word : null));
                //The below list is to capture the optimized list
                if (isObscene)
                    abbreviatedList.Add(word.ToUpper());
            }
            iter = _root;
        }

        //Purely for fixing a non-optimized list
        //Remove once list is optimized
        var output = String.Empty;
        for (var i = 0; i < abbreviatedList.Count(); i += 10)
        {
            var segment = abbreviatedList.Skip(i).Take(10);
            output += "\"" + String.Join("\",\"", segment) + "\"," + Environment.NewLine;
        }
    }

    //Finally the actual IsObscene check that loops through the tree.
    public static bool IsObscene(string text)
    {
        var iters = new List<ObsceneNode>(text.Length);
        for (var i = 0; i < text.Length; i++)
        {
            iters.Add(_root);
            var c = text[i];

            for (int j = iters.Count() - 1; j >= 0; j--)
            {
                if (iters[j].HasChild(c))
                {
                    iters[j] = iters[j].GetChild(c);
                    if (iters[j].Value.IsObscene)
                    {
                        return true;
                    }
                }
                else
                {
                    iters.RemoveAt(j);
                }
            }
        }

        return false;
    }