Anagram finder in C#

This is the C# implementation of the anagram program. The problem and the solution is described in the main anagram article. Do read that article first.

Also, you may find the C++ article helpful, since it describes member data and functions in some detail, not repeated here. This article describes only the differences between the C++ implementation and this implementation.

Actually C# and C++ implementations are virtually identical. The differences are syntactical only.

The words comparison could have been inlined, but that is hard on the eyes.

The source code

using System;
using System.Collections.Generic;

namespace Anagram {

    class Word {
        public int    offset;
        public String value;
        public String unified;

        public Word(int offset, String value, String unified) {
            this.offset  = offset;
            this.value   = value;
            this.unified = unified;
        }

        public override string ToString() {
            return String.Format("{0:d4} {1} {2}", offset, value, unified);
        }
    }

    class WordCompare : IComparer<Word> {
        public static int comparisons;
        public int Compare(Word a, Word b) {
            comparisons++;
            int rval = a.unified.CompareTo(b.unified);
            return (0 != rval) ? rval : (a.offset - b.offset);
        }
    }

    class AnagramFinder {
        private int        len;
        private Word[]     words;
        private List<Word> accepted = new List<Word>();
        private int        low_offset = 0;

        public AnagramFinder(String text, int len) {
            int last = text.Length - len;
            this.words = new Word[last+1];
            this.len   = len;
            for (int n = 0; n <= last; n++) {
                String value = text.Substring(n, len);
                words[n] = new Word(n, value, get_unified(value));
            }
        }

        private static string get_unified(String value) {
            char[] chars = value.ToCharArray();
            Array.Sort(chars);
            return new String(chars);
        }

        private void print_one_result() {
            Console.Write("{0,3:d}:", accepted.Count);
            foreach (var it in accepted)
                Console.Write(" {0,4:d}:{1}", it.offset, it.value);
            Console.WriteLine();
        }

        private void add_candidate(Word cand) {
            if (cand.offset < low_offset)
                return;
            foreach (var it in accepted)
                if (cand.value.Equals(it.value))
                    return;
            accepted.Add(cand);
            low_offset = cand.offset + len;
        }

        private void add_range(int begin, int end) {
            if (end-begin >= Program.MINIMUM) {
                accepted.Clear();
                low_offset = 0;
                for (int n = begin; n < end; n++)
                    add_candidate(words[n]);
                if (accepted.Count >= Program.MINIMUM)
                    print_one_result();
            }
        }

        public void find_all() {
            Array.Sort(words, new WordCompare());
            int begin = 0;
            for (int n = 1; n < words.Length; n++) {
                if (! words[begin].unified.Equals(words[n].unified)) {
                    add_range(begin, n);
                    begin = n;
                }
            }
            add_range(begin, words.Length);
        }
    }

    class Program {
        public const int MINIMUM = 3;

        static String read_text() {
            var buf = new System.Text.StringBuilder();
            int b;
            while ((b = Console.In.Read()) >= 0) {
                char ch = (char)b;
                if (Char.IsLetter(ch))
                    buf.Append(Char.ToUpper(ch));
            }
            return buf.ToString();
        }

        static void Main(string[] args) {
            String text = read_text();
            int from = (args.Length >= 1) ? Int32.Parse(args[0]) : 4;
            int to   = (args.Length >= 2) ? Int32.Parse(args[1]) : from;
            for (int n = from; n <= to; n++) {
                Console.WriteLine("{0}len = {1}", (n > from ? "\n" : ""), n);
                new AnagramFinder(text, n).find_all();
            }
            Console.WriteLine("string length = {0,5:d}, comparisons = {1,5:d}",
                              text.Length, WordCompare.comparisons);
        }
    }
}

You can reach me by email at “lars dash 7 dot sdu dot se” or by telephone +46 705 189090

View source for the content of this page.