using System.Collections.Generic;
public class TotalPatternCount
public class PatternSearcher
private static string FindOverlap(string input, int index, int patternLength)
var newPatternLength = patternLength * 2 - 2;
var len = Math.Min(newPatternLength, input.Length - (index + 1));
return input.Substring(index + 1, len);
private static void DecreaseOverlaps(Dictionary<string, TotalPatternCount> patterns, string pattern, int patternLength)
var input = patterns[pattern].Overlap;
while (i + patternLength <= input.Length)
string overlapFound = input.Substring(i, patternLength);
if (patterns.ContainsKey(overlapFound))
patterns[overlapFound].Counter -= 1;
if (patterns[overlapFound].Counter <= 0 && pattern != overlapFound)
patterns.Remove(overlapFound);
public static Dictionary<string, TotalPatternCount> CountPatterns(string input, int patternLength)
throw new ArgumentOutOfRangeException("patternLength expected >= 0 but found {patternLength} instead.");
if (input == null || input.Length == 0)
throw new ArgumentException("Please enter non empty string as input.");
var patterns = new Dictionary<string, TotalPatternCount>();
while (i + patternLength <= input.Length)
string pattern = input.Substring(i, patternLength);
if (patterns.ContainsKey(pattern))
patterns[pattern].Counter = patterns[pattern].Counter + 1;
DecreaseOverlaps(patterns, pattern, patternLength);
patterns[pattern].Overlap = FindOverlap(input, i, patternLength);
var overlap = FindOverlap(input, i, patternLength);
patterns[pattern] = new TotalPatternCount{Pattern = pattern, Counter = 1, Overlap = overlap};
public static List<TotalPatternCount> FilterAboveCount(Dictionary<string, TotalPatternCount> patterns)
var resultsList = new List<TotalPatternCount>();
foreach (var item in patterns)
if (item.Value.Counter >= 2)
resultsList.Add(item.Value);
public static void Main()
Console.WriteLine("Enter string:");
var searchString = Console.ReadLine();
Console.WriteLine("Enter Pattern Length:");
if (int.TryParse(Console.ReadLine(), out patternLength))
var results = FilterAboveCount(CountPatterns(searchString, patternLength));
Console.WriteLine("Found the following patterns greater than 1 match:");
foreach (var item in results)
Console.WriteLine(item.Pattern + " has occurance of " + item.Counter);
Console.WriteLine("Please input a valid number for patternLength");
Console.WriteLine("Press any key try again");
Console.WriteLine("__________________________");