OP said it could also be deletions and insertions. So the xor trick won't work. Without more information from OP, we can only guess, but I was guessing this was a genetics problem trying to build DNA sequences from fragments, and the mention of base64 was just mock data to test the algorithm. If the data can have random insertions, deletions, and swaps, then you need the full DP algorithm. *IF* the number of acceptable errors is low, then yes you can short-circuit it and maybe end up close to linear, but then there's stil the added complexity of deciding how much overlap gives the best result.