How to do spell check through hashing?

Question

Python

I ask you to help with the solution of the problem, otherwise I have been sitting for more than 4 hours and I can’t understand in any way.
TIME LIMIT -2 seconds. Input string values ​​up to 10^6 long
Task:
Petya noticed that when he types on the keyboard, extra keys are often pressed and extra letters appear in words. Of course, the spelling system underlines these words for him, he has to click on the word and choose the correct option. Petya was tired of correcting his mistakes manually, so he decided to implement a function that would make corrections on its own. Petya began by analyzing the most common case for him, when it is enough to remove one letter from a word so that it coincides with some word from the dictionary. So, Petya faced the following subtask: given the entered word and the word from the dictionary, you need to remove one letter from the first word to get the second one. And then a very non-trivial question arose before Petya: which letter to delete?
Input data:
The input contains two strings consisting of lowercase Latin letters. The length of the lines is from 1 to 10^6 characters inclusive, the first line contains exactly 1 character more than the second.
Output:
In the first line print the number of character positions in the first line, removing each of which results in the second line. In the second line print the positions themselves in ascending order separated by a space. Positions are numbered starting from 1. If it is impossible to get the second from the first line by deleting one character, print a single number 0.
Example
input
abdrakadabra
abrakadabra
output:
1
3

Answer 1

There is a solution to this problem in C++ (hello, Tinkoff):

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
 
using namespace std;
 
typedef unsigned long long ull;
 
const int MAGIC = 10007;
const int MAXL = 1111111;
 
char s[MAXL], t[MAXL];
ull pre_s[MAXL], pre_t[MAXL], suf_s[MAXL], suf_t[MAXL];
 
inline void get_hash(char* s, ull* pre, ull* suf) {
  int n = strlen(s);
  pre[0] = s[0];
  for (int i = 1; i < n; ++i)
    pre[i] = pre[i - 1] * MAGIC + s[i];
  suf[n - 1] = s[n - 1];
  for (int i = n - 2; i >= 0; --i)
    suf[i] = suf[i + 1] * MAGIC + s[i];
}
 
int main() {
  gets(s);
  gets(t);
  get_hash(s, pre_s, suf_s);
  get_hash(t, pre_t, suf_t);
  int m = strlen(s);
  vector<int> ans;
  for (int i = 0; i < m; ++i)
    if ((i == 0 || pre_s[i - 1] == pre_t[i - 1]) && (i == m - 1 || suf_s[i + 1] == suf_t[i]))
      ans.push_back(i + 1);
  printf("%d\n", (int)ans.size());
  if (ans.size()) {
    printf("%d", ans[0]);
    for (int i = 1; i < (int)ans.size(); ++i)
      printf(" %d", ans[i]);
    printf("\n");
  }
}

Answer 2

line = 'abdrakadabra'
etalon = 'abrakadabra'

x = 0
mistake = 0
new_line=''
try:
    for _ in line:
        if _ == etalon[x]:
            new_line += _
        else:
            mistake = x
            x-=1
        x+=1
except:
    pass

print(mistake+1)

Answer 3