The KMP Algorithm

Not difficult to understand. I learned it from Coursera.

Prefix Function

• A “Border” of a string, is a substring that both acts as a prefix and a suffix of that string
• The “Prefix Function” of a string records the length of the longest border of every prefix of that string

Symbol

• s is a string
• s[:i] is a prefix of s made up by s[0], s[1], ..., s[i-1]
• L[i] is the length of the longest border of s[:i]
  • In other words, L is the “Prefix Function” of s

Conclusion

1. L[i+1] <= L[i]+1, and the equality holds if and only if s[L] = s[i]
2. The longest border of the longest border of a string, is the second longest border of that string.
3. if some border of s[:i] has a length of len and s[len] = s[i], then there must be a border in s[:i+1] with a length of len+1

Method

1. L[0] = 0
2. L[i+1] = len + 1, where len is the length of the longest border of s[:i] that satisfies s[len] = s[i]
   • To find len, try every border of s[:i] from the longest to the shortest
   • To find the next longest border, see Conclusion 2
   • If no border is found, simply compare s[0] with s[i]
   • If s[0] = s[i], then L[i+1] = 1
   • Else, L[i+1] = 0

Implementation

int *pf(string s) {
	int len=s.size(),b=0;
	int *p=new int[len]; p[0]=0;
	for(int i=1;i<len;i++) {
		while(b>0 && s[i]!=s[b]) b=p[b-1];
		if(s[i]==s[b]) b++;
		p[i] = b;
	}
	return p;
}

KMP

Symbol

• p is the pattern string, t is the text string
• L is the “Prefix Function” of p

Conclusion

• If p matches t partially with a longest common prefix p[:i], then no matches will be found before p is shifted len(p) - L[i] positions rightwards.
  • There are two “submatches” in this partial match, both of which are the longest border of p[:i]
  • The left one acts as a prefix, while the right one acts as a postfix
  • p is shifted rightwards, so does p[:i]
  • No matches are possible before the left submatch arrives at the previous position of the right submatch
  • The length of this “vacuum area” is len(p) - L[i]

Method

1. Make s = p + '$' + t, where ‘$’ is absent from both p and t
2. Calculate the “Prefix Function” of s, marked as L
3. A match is found at position i - 2 * len(p) when L[i] = len(p)
   • Under such circumstances, the longest border of s[:i] happens to be p itself, as p is a prefix of s
   • This border is also a substring of s
   • Thanks to the ‘$’ sign, we can guarantee that this border never crosses the real “border” between p and t, so it is also a substring of t
   • Thus the starting position of the match is i - (len(p) - 1) in s, and i - (len(p) - 1) - (len(p) + 1) in t

Implementation

int main() {
	string pattern, text, s;
	int *pf;
	while(cin >> pattern >> text && pattern != "") {
		if(pattern.size() > text.size()) {
			cout << "-1" << endl;
			continue;
		}
		s = pattern + "$" + text;
		pf = prefix_func(s);
		for(int i = pattern.size()+1; i < s.size(); i++) {
			if(pf[i] == pattern.size()) {
				cout << i - 2 * pattern.size() << " ";
			}
		}
		cout << endl;
		delete pf;
	}
	return 0;
}