Find common prefix of a list of strings.

prefix.py

#!/usr/bin/env python3

def find_prefix(words):
	it = iter(words)
	try:
		first = next(it)
	except StopIteration:
		return ''

	if not first:
		return ''

	plen = len(first)
	for other in it:
		plen = min(len(other), plen)
		for i in range(plen):
			if first[i] != other[i]:
				plen = i
				break
		
		if plen == 0:
			return ''

	return first[:plen]

if __name__ == '__main__':
	import sys
	prefix = find_prefix(line.rstrip() for line in sys.stdin)
	print(prefix)

Its written so that the word list can be a generator.

Algorithm:

• (if the supplied list is empty, the prefix is the empty string)
• take first word
• (shortcut: if the word is empty the prefix is empty)
• initial prefix length is the length of the first word
• for each other word:
  • if the new word is shorter than the current prefix length the new prefix length has to be truncated to that length
  • find the first character of the new word within the current prefix length that is different to the character of the same index of the first word
  • if there is such a character the new prefix length is its index
  • (shortcut: if the new prefix length is 0 the prefix is the empty string)
• the prefix is the slice of the first word up to the calculated prefix length