At first special thanks to @jianchao.li.fighter's introduction to KMP algorithm and 2 helpful links in his answer to this problem. Here is his answer: https://leetcode.com/discuss/38998/explained-4ms-easy-c-solution and below are the 2 links to refer to.

- http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
- http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

**For those who don't know what KMP is please read the content in the 2 links first**. And here I just add some detailed supplementary comments on how to build up the lps[] based on the original code and comments from the 2nd link. Hope this will help those who are still confused how the lps[] is built (especially for the tricky part) after read the content in the 2 links above.

```
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // lenght of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
//example "abababca" and i==5, len==3. The longest prefix suffix is "aba", when pat[i]==pat[len],
//we get new prefix "abab" and new suffix "abab", so increase length of current lps by 1 and go to next iteration.
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
len = lps[len-1];
//This is tricky. Consider the example "ababe......ababc", i is index of 'c', len==4. The longest prefix suffix is "abab",
//when pat[i]!=pat[len], we get new prefix "ababe" and suffix "ababc", which are not equal.
//This means we can't increment length of lps based on current lps "abab" with len==4. We may want to increment it based on
//the longest prefix suffix with length < len==4, which by definition is lps of "abab". So we set len to lps[len-1],
//which is 2, now the lps is "ab". Then check pat[i]==pat[len] again due to the while loop, which is also the reason
//why we do not increment i here. The iteration of i terminate until len==0 (didn't find lps ends with pat[i]) or found
//a lps ends with pat[i].
}
else // if (len == 0)
{ // there isn't any lps ends with pat[i], so set lps[i] = 0 and go to next iteration.
lps[i] = 0;
i++;
}
}
}
}
```