Как сделать проверку правописания через хеширование?

Question

[overlord1337]

Прошу помочь с решением задачи, а то уже больше часов 4 сижу и никак понять не могу.
ОГРАНИЧЕНИЕ ПО ВРЕМЕНИ -2 секунды. Входные значения строки длиной до 10^6
Задача:
Петя заметил, что когда он набирает текст на клавиатуре, у него часто нажимаются лишние клавиши и в словах возникают лишние буквы. Конечно же, система проверки правописания подчеркивает ему эти слова, ему приходится кликать на слово и выбирать правильный вариант. Пете надоело исправлять свои ошибки вручную, поэтому он решил реализовать функцию, которая сама будет вносить исправления. Петя начал с разбора наиболее часто встречающегося у него случая, когда из слова достаточно удалить одну букву, чтобы оно совпало с некоторым словом из словаря. Итак, Петя столкнулся с такой подзадачей: дано введенное слово и слово из словаря, нужно удалить из первого слова одну букву, чтобы получилось второе. И тогда перед Петей встал весьма нетривиальный вопрос: какую букву удалять?
Входные данные:
Входные данные содержат две строки, состоящие из строчных латинских букв. Длина строк от 1 до 10^6 символов включительно, первая строка содержит ровно на 1 символ больше, чем вторая.
Выходные данные:
В первой строке выведите количество позиций символов в первой строке, при удалении каждого из которых получается вторая строка. Во второй строке через пробел выведите сами позиции в порядке возрастания. Позиции нумеруются с 1. Если из первой строки невозможно получить вторую путем удаления одного символа, выведите одно число 0.
Пример
входные данные
abdrakadabra
abrakadabra
выходные данные:
1
3

Comments

[Saboteur]

А причем тут хеширование?

[overlord1337]

Saboteur, там асимптотика алгоритма по идеи должна быть O(n+m) (вроде как) , написание данного алгоритма с такой асимптотикой можно сделать ток через хеширование)

Answer 1

[ZIK1337]

На с++ есть решение этой задачи (привет, тинькофф):

#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");
	}
}

Comments

[overlord1337]

спасиб)

Answer 2

[Alexa2007]

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)

Comments

[longclaps]

Хороший код, Alexa2007, можно сказать, etalon. Бессмысленный, бесполезный, но очень хороший.

Answer 3

[Andrey Dugin]

Comments

[longclaps]

Как водится, решение никуда не годится.
Пример:
a = 'a' * 10
b = 'a' * 9

Выходные данные:
В первой строке выведите количество позиций символов в первой строке, при удалении каждого из которых получается вторая строка. Во второй строке через пробел выведите сами позиции в порядке возрастания.

Очевидно, что ответом будет

10
1 2 3 4 5 6 7 8 9 10

А Андрюша выводит чёрте что.

[Andrey Dugin]

longclaps, а это и не решение, а всего лишь указание на инструмент, который можно применять. Ответ даётся абсолютно корректный - удалить последний символ. Осталось только отформатировать его к тому виду, который требуется в задаче:

Просто кто-то не умеет пользоваться библиотеками Python)