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

    ZIK1337
    @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");
    	}
    }
    Ответ написан
    1 комментарий