Skip to content

Instantly share code, notes, and snippets.

@DareDev1l DareDev1l/Words.cs
Created Dec 5, 2015

Embed
What would you like to do?
namespace _06.Words
{
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Text;
class StartUp
{
public static void Main()
{
int result = 0;
string word = Console.ReadLine();
string stringToLook = Console.ReadLine();
char[] WordAsCharArray = word.ToCharArray();
char[] S = stringToLook.ToCharArray();
var prefixesAndSufixes = GetPrefixAndSufix(word);
//strings longer than 2 chars
foreach(var pair in prefixesAndSufixes)
{
var stringSearcherPrefixes = new StringSearcher(pair.Key.ToCharArray());
int prefixesFound = stringSearcherPrefixes.Search(S);
var stringSearcherSufixes = new StringSearcher(pair.Value.ToCharArray());
int sufixesFound = stringSearcherSufixes.Search(S);
//Console.WriteLine("{0} * {1} = {2}", prefixesFound, sufixesFound, prefixesFound * sufixesFound);
result += (prefixesFound * sufixesFound);
}
// w,ord
int prefixWithOneChar = NumberOfCharInString(word[0], stringToLook);
var stringSearchSuffixOfOneChar = new StringSearcher(word.Substring(1).ToCharArray());
int restOfSuffix = stringSearchSuffixOfOneChar.Search(S);
// Console.WriteLine("{0} * {1} = {2}", prefixWithOneChar, restOfSuffix, prefixWithOneChar * restOfSuffix);
result += (prefixWithOneChar * restOfSuffix);
// wor,d
int sufixWithOneChar = NumberOfCharInString(word[word.Length - 1], stringToLook);
var firstPart = word.Substring(0, word.Length - 1).ToCharArray();
var stringSearchPrefixOfOneChar = new StringSearcher(firstPart);
int restOfPrefix = stringSearchPrefixOfOneChar.Search(S);
//Console.WriteLine("{0} * {1} = {2}", sufixWithOneChar, restOfPrefix, sufixWithOneChar * restOfPrefix);
result += sufixWithOneChar * restOfPrefix;
StringSearcher completeWordSearch = new StringSearcher(WordAsCharArray);
int matchesCount = completeWordSearch.Search(S);
//Console.WriteLine("Full word: {0}", matchesCount);
result += matchesCount;
Console.WriteLine(result);
}
public static int NumberOfCharInString(char c, string s)
{
int occurances = 0;
for (int i = 0; i < s.Length; i++)
{
if(s[i] == c)
{
occurances++;
}
}
return occurances;
}
public static List<KeyValuePair<string, string>> GetPrefixAndSufix(string stringW)
{
var listOfPrefixAndSuffix = new List<KeyValuePair<string, string>>();
for (int i = 0; i < stringW.Length; i++)
{
string prefix = string.Empty;
string suffix = string.Empty;
for (int j = 0; j < i; j++)
{
prefix += stringW[j];
}
for (int j = i; j < stringW.Length; j++)
{
suffix += stringW[j];
}
if(prefix.Length >= 2 && suffix.Length>=2)
{
listOfPrefixAndSuffix.Add(new KeyValuePair<string, string>(prefix, suffix));
}
}
return listOfPrefixAndSuffix;
}
}
// https://jamesmccaffrey.wordpress.com/2012/08/18/the-knuth-morris-pratt-string-search-algorithm-in-c/
public class StringSearcher // Knuth-Morris-Pratt string search
{
private char[] WordLookedFor; // the (small) pattern to search for
private int[] T; // lets the search function to skip ahead
public StringSearcher(char[] WordLookedFor)
{
this.WordLookedFor = new char[WordLookedFor.Length];
Array.Copy(WordLookedFor, this.WordLookedFor, WordLookedFor.Length);
this.T = BuildTable(WordLookedFor); // use a helper to build T
}
private int[] BuildTable(char[] W)
{
int[] result = new int[W.Length];
int pos = 2;
int cnd = 0;
result[0] = -1;
result[1] = 0;
while (pos < W.Length)
{
if (W[pos - 1] == W[cnd])
{
++cnd; result[pos] = cnd; ++pos;
}
else if (cnd > 0)
cnd = result[cnd];
else
{
result[pos] = 0; ++pos;
}
}
return result;
}
public int Search(char[] WordWeLookFor)
{
// Here is the variable for the count of words
int matchesOfWord = 0;
// look for this.W inside of S
int m = 0;
int i = 0;
while (m + i < WordWeLookFor.Length)
{
if (this.WordLookedFor[i] == WordWeLookFor[m + i])
{
if (i == this.WordLookedFor.Length - 1)
{
// Word found - update counter
matchesOfWord++;
// we don't return m here as in original solution, but continue the cycle - so update m to look for words after this index.
// This code below is exact copy of the else below the if. It's like we didn't found anything on this position and we continue with the code
m = m + i - this.T[i];
if (this.T[i] > -1)
i = this.T[i];
else
i = 0;
}
++i;
}
else
{
m = m + i - this.T[i];
if (this.T[i] > -1)
i = this.T[i];
else
i = 0;
}
return matchesOfWord; // not found
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.