# Aho–Corasick Algorithm

Aho–Corasick algorithm is a string searching algorithm. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously.

```									```private const int MaxStates = 6 * 50 + 10;
private const int MaxChars = 26;

private static int[] Out = new int[MaxStates];
private static int[] FF = new int[MaxStates];
private static int[,] GF = new int[MaxStates, MaxChars];

private static int BuildMatchingMachine(string[] words, char lowestChar = 'a', char highestChar = 'z')
{
Out = Enumerable.Repeat(0, Out.Length).ToArray();
FF = Enumerable.Repeat(-1, FF.Length).ToArray();

for (int i = 0; i < MaxStates; ++i)
{
for (int j = 0; j < MaxChars; ++j)
{
GF[i, j] = -1;
}
}

int states = 1;

for (int i = 0; i < words.Length; ++i)
{
string keyword = words[i];
int currentState = 0;

for (int j = 0; j < keyword.Length; ++j)
{
int c = keyword[j] - lowestChar;

if (GF[currentState, c] == -1)
{
GF[currentState, c] = states++;
}

currentState = GF[currentState, c];
}

Out[currentState] |= (1 << i);
}

for (int c = 0; c < MaxChars; ++c)
{
if (GF[0, c] == -1)
{
GF[0, c] = 0;
}
}

List<int> q = new List<int>();
for (int c = 0; c <= highestChar - lowestChar; ++c)
{
if (GF[0, c] != -1 && GF[0, c] != 0)
{
FF[GF[0, c]] = 0;
}
}

while (Convert.ToBoolean(q.Count))
{
int state = q[0];
q.RemoveAt(0);

for (int c = 0; c <= highestChar - lowestChar; ++c)
{
if (GF[state, c] != -1)
{
int failure = FF[state];

while (GF[failure, c] == -1)
{
failure = FF[failure];
}

failure = GF[failure, c];
FF[GF[state, c]] = failure;
Out[GF[state, c]] |= Out[failure];
}
}
}

return states;
}

private static int FindNextState(int currentState, char nextInput, char lowestChar = 'a')
{
int c = nextInput - lowestChar;

{
}

}

public static List<int> FindAllStates(string text, string[] keywords, char lowestChar = 'a', char highestChar = 'z')
{
BuildMatchingMachine(keywords, lowestChar, highestChar);

int currentState = 0;
List<int> retVal = new List<int>();

for (int i = 0; i < text.Length; ++i)
{
currentState = FindNextState(currentState, text[i], lowestChar);

if (Out[currentState] == 0)
continue;

for (int j = 0; j < keywords.Length; ++j)
{
if (Convert.ToBoolean(Out[currentState] & (1 << j)))
{
retVal.Insert(0, i - keywords[j].Length + 1);
}
}
}

return retVal;
}```
```

### Example

```									```string[] keywords = { "he", "she", "hers", "his" };

string text = "ahishers";

List<int> states = FindAllStates(text, keywords);```
```

### Output

```									```4
3
4
1```
```