"The Ministry of Truth" challenge
For the overall program structure, I suggest:


Using fileinput instead of explicitly using sys.argv[1].  Your program would automatically switch between sys.stdin and the named file.
Breaking out the redaction logic into its own function, because each line is a self-contained problem with well-defined inputs and outputs.


To perform the redaction, I suggest using regular expressions, since this is just a pattern-matching problem.  You've used the re module already, so you might as well go all the way.

import fileinput
import re

def redact(original, target):
    matched = False
    def replacement(m):
        matched = True
        s = list(m.string)
        for g in range(1, 1 + len(m.groups())):
            for i in range(m.start(g), m.end(g)):
                s[i] = ' ' if s[i] == ' ' else '_'
        return ''.join(s)

    # Replace contiguous spaces with one space
    original = re.sub(r"\s+", " ", original)
    pattern = re.compile(
        '^(.*?)' +
        '( .*?|.*? )'.join(re.escape(c) for c in target.split(' ')) +
        '(.*?)$'
    )
    result = pattern.sub(replacement, original)
    return 'I cannot fix history' if matched else result

if __name__ == '__main__':
    for line in fileinput.input():
        line = line.strip()
        if not line:
            continue
        print(redact(*line.split(';', 1)))