Finding the index of a set of characters in huge sequence of characters
hashmap, java, sequence
Solution
This is a classic problem call the longest common subsequence (LCS). There are many algorithms to solve it. The genome project does this kind of search a lot. The wiki link provided has many examples. Your threshold for errors would be a special case.
Are you doing something with gene sequencing? I ask only because you mention only 4 variables :)
Problem
Let's say I have an extremely large sequence of characters of A-D, 4 Billion to be exact. My goal is to find the indexes of several new sequences of letters that are set at length 30 within that large sequence of characters. The problem also increases in difficulty when the sequence you are looking for has a small error (a letter is wrong). How should I tackle this problem? The trivial method is to iterate one letter at a time across the whole 4 Billion text file, but that'll take forever with memory running out. I've been told to utilize a hashmap, but I'm not sure exactly what to use as my key value pair. The idea of using regex has also come up, but I'm not entirely sure if it'll work with my problem. Any help in terms of direction would be appreciated. Thanks! Here's an illustration of what I'm asking: