KMP (Knuth-Morris-Pratt) is a string matching algorithm for finding the occurrences of a pattern in a string. Unlike brute force algorithm, which shifts only one character if not matching, KMP uses a smarter way for shifting by skipping unnecessary check.

It finds what is the longest possible shift to avoid wasteful comparisons. which is the largest prefix of `P[0 .. j-1]`

that is a suffix of `P[1 .. j-1]`

where `P`

is the pattern. Because it will be used multiple times especially if the string is long, it's better to compute and store the largest identical prefix suffix at each index.

## Computing Longest Prefix Suffix (LPS)

Before going to the algorithm, I'll give you an example. For example, the pattern is *abaab*. At the first character, the LPS is always 0 because suffix must always start at least from index 1 (the second character). Move to the next index and now we have *ab* substring. Clearly those two characters aren't the same, so the LPS is 0 too. At index 2 where the substring is *aba*, we can get *a* (the first character) as the prefix and *a* (the third character) as the suffix, so the LPS is a whose length is 0. At the index 4, the LPS is *ab* (the first two and last two characters). That's an example how to compute LPS.

The algorithm for finding longest suffix prefix is not long, but a bit tricky. If we use 0 (not 1) as the first character index `i`

, there is a loop from `i = 0`

until `i = m`

, where `m`

is the pattern length. We have another variable `j`

which holds the current longest prefix suffix. While `i < m`

, if the character at `j`

equals the character at `i`

, it means the LPS at the index is the value of `j + 1`

and we can increment the value of `j`

and `i`

. Else, if the character at `j`

doesn't equal the character at `i`

and `j > 0`

, update the value of `j`

to use the LPS at `j - 1`

. We need to handle the case where `j`

equals 0. If that happens, it means the LPS at the index is 0 and we can move to the next index.

```
List computeLPS(String pattern) {
List lps = new List(pattern.length);
lps[0] = 0;
int m = pattern.length;
int j = 0;
int i = 1;
while (i < m) {
if (pattern[j] == pattern[i]) {
lps[i] = j + 1;
i++;
j++;
} else if (j > 0) {
j = lps[j-1];
} else { // no match
lps[i] = 0;
i++;
}
}
return lps;
}
```

And below is the implementation of KMP algorithm. The `computeLPS`

function is called first before the iteration.

```
List<int> kmp(String text, String pattern) {
List<int> foundIndexes = new List<int>();
int n = text.length;
int m = pattern.length;
int i = 0;
int j = 0;
List lps = computeLPS(pattern);
while (i < n) {
if (pattern[j] == text[i]) {
i++;
j++;
}
if (j == m) {
foundIndexes.add(i - m); // Match
print(j);
j = lps[j - 1];
i += m - 1;
} else if (i < n && pattern[j] != text[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i = i + 1;
}
}
}
return foundIndexes;
}
main() {
print(kmp('ABCABCDEFGABC', 'ABC')); // Output: [0, 3, 10]
print(kmp('AAAAAAAAAAAAAAABBCCDDAAA', 'AAAA')); // Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(kmp('AAAABBCCDDAAA', 'ABAAB')); // Output: []
}
```

This Knuth-Morris-Pratt algorithm implementation in Dart returns the list of indexes where the pattern found. There is a loop as many as the text length. Variable `i`

stores the current text index, while variable `j`

stores the current pattern index. `m`

is the pattern length, while `n`

is the text length. At every index, we compare the value of pattern at index `j`

and text at index `i`

. If the two characters are the same, the potential to get match is still alive and we increment the value of `i`

and `j`

by one. If it has reached the last pattern character, it means we found a match. If the two characters are different and `j > 0`

, assign `j`

with the value of LPS at `j - 1`

. It means we don't need to compare from the beginning. If `j`

is 0, just increment the `i`

value to check the next text character.

As you can see on the output, for the second example, it returns the presence of pattern *AAAA* at every index the pattern matches. It means there are some overlaps in the result. If you don't want to get overlapped result, you can add `i += m - 1`

; when a match is found.