Which results are known about the string edit distances using the edition operator "Search and Replace"?
Edit distances were traditionally used in bio informatics and to correct typographical errors, and many edit distances (e.g. the "Delete, Insert, Replace" edit distance, aka Levenshtein distance) can be computed in quadratic time via dynamic programming. Some people seem to be using the Levenshtein distance to detect copies by students in online exam answers, which seem wrong: a few search and replace queries can arbitrarily increase the Levenshtein distance between the original answer and it's edited copy.
I believe that edit distances including an operator where all occurrences of a token (letter, word, block, your pick) are replaced by another token, with unitary cost per operation (corresponding to the constant time for a human to instruct a computer to perform such operation), would be more useful in the detection of such plagiarism (and in version control systems too, by the way). Combined with some linear preprocessing of the strings, such edit distances do not seem too prohibitively costly to compute either.
Yet, an internet search for "search and replace Edit distance" returned only unrelated results (e.g. a search and replace operators conditioned by edit distance, https://github.com/soodoku/Search-And-Replace). I am wondering if it already exists but under another name, or if I am mistaken about its difficulty (or if I should go on and work on it)!. Anybody who could let me know if I reinvented the wheel, just under a new name, or if my wheel is actually a square would save me much time!