Approximate string search in Python
Since there is no answer yet - what I would try:

I would search words rather than characters. make a dictionary of words (bag of words) and count the frequency. your test bag of words should be a subset of the source bag of words mostly. by comparing to other sources you could analyze relevance of words and other measures.

The big advantage of words vs. characters is that the comparison resyncs with every whitespace. an insertion/deletion of a character will result in a single changed word. you are now talking in edit distance of words, rather than characters. so translate your strings to arrays of words (whatever representation you use for a word (sequential number, hash, reference, ...).

Now slide your test words over the source words and count the number of word matches. for your parameters this will be around 1,000 word over 1,000,000 words, which sounds reasonable. you get an array of match counts with length 1,000,999. it will have the following properties


some noise floor of matches. the most frequent words of your language match by accident
some (at least one) entries greater or equal to the longest matching subsequence
some 'distribution' (near gaussian?) caused by inserted/deleted words indicating where to find your test file


this would be less heuristic than your approach, although you probably will again apply some more algorithms/heuristics to find the 'exact' match start/end.



EDIT: I simply had to try the bag of words approach

I simply slide a window of the probe words length ofer the text words in single word steps. for this text window i calculate the bag of words and compare it to the probe and sum the absolute difference values for every entry.

e. g.: 'so the the moon' vs. 'the moon moon is' resulting (so:1 the:2 moon:1) vs. (the:1 moon:2 is:1) wich results in a diff (so:1 the:1 moon:-1 is:-1) in absolute values (so:1 the:1 moon:1 is:1) summing up to the value 4.

This measure for my test set


text size 100,000 chars (~ 16,000 words)
probe size 6,000 chars (~ 1,000 words)
probe edits (change, insert, delete) 300 chars (letters, digits, punctuation, whitespace)
bag size for a 1000 words window from text ~ 500 words with frequencies from 20+ down to 1
bag size of the (edited) probe ~ 600 words


gives the following result



This looks pretty robust to me. We see


for the best match a word-edit-distance of 460 (inserting a whitespace may results in a distance of 3)
for a non-matching region a word-edit-distance of 1200
a near linear transition double as wide as the probe size


See the transition scaled up