# Finite-State Automaton

Finite-State Automaton is a string searching algorithm.

```									```public static int[] SearchString(string str, string pat)
{
List<int> retVal = new List<int>();
int M = pat.Length;
int N = str.Length;
int i, state = 0;
int[,] TF = new int[M + 1, 256];

ComputeTF(pat, M, TF);

for (i = 0; i < N; i++)
{
state = TF[state, str[i]];

if (state == M)
{
}
}

return retVal.ToArray();
}

private static void ComputeTF(string pat, int M, int[,] TF)
{
int state, x;

for (state = 0; state <= M; ++state)
for (x = 0; x < 256; ++x)
TF[state, x] = GetNextState(pat, M, state, x);
}

private static int GetNextState(string pat, int M, int state, int x)
{
if (state < M && x == pat[state])
return state + 1;

int ns, i;

for (ns = state; ns > 0; ns--)
{
if (pat[ns - 1] == x)
{
for (i = 0; i < ns - 1; i++)
{
if (pat[i] != pat[state - ns + 1 + i])
break;
}

if (i == ns - 1)
return ns;
}
}

return 0;
}```
```

### Example

```									```string data = "the quick brown fox jumps over the lazy dog";
int[] value = SearchString(data, "the");```
```

### Output

```									```0
31```
```