В строке, где выводишь индексы в ответ, res должен выглядеть так:
ll res=((h[i+tz-1]-h[i-1]*x[tz]+mod)%mod + mod) % mod;
Т.к. ты в этой строчке вычитаешь, у тебя может выйти отрицательное число, а значит дальше пойдет не тот результат взятия по модулю.
Вообще советую в задачах на хеши создавать отдельную структуру для чисел, где перегруженные операторы будут автоматически результат по модулю брать, кучу времени на дебаг спасешь)
@eudaimon can you analyze azatu’s code and give him any specific recommendations? do not give general advice, tailor your response to his specific code.
@Anton, I’ll focus on the specific code provided by azatu and analyze the potential issues with it.
Looking at the code snippet, azatu is implementing a solution to a string hashing problem, where the goal is to find all the occurrences of string t in string s with exactly one character allowed to differ. Here are some specific recommendations:
Optimization with unordered_map:
You’ve already switched from set<ll> to unordered_map<ll, ll>, which is good for improving average time complexity from O(log n) to O(1) on hash table operations. However, the issue may not be with the data structure, but with how many elements you’re inserting into it. Since you’re hashing every possible single-character modification of t, this can be very large.
Potential Integer Overflow:
Ensure there’s no integer overflow when performing operations like h_t[i-1]*x[tz-i+1]. The multiplication might exceed the bounds of a long long before you take the modulo. You might want to cast the operands to a larger type or use a modular multiplication function.
Check the Hashing Logic:
Double-check the logic behind how you generate the hashes, especially the parts where you add and subtract and then take the modulo. Hashing is very sensitive to small mistakes, and an off-by-one error or incorrect modular arithmetic can lead to wrong results.
Debugging with Known Test Cases:
Use known test cases where you know the expected output. Step through your code using a debugger or print statements to ensure each part of your code is functioning as you expect.
Corner Cases:
Make sure you handle corner cases. For example, when tz > sz, you correctly return “0”, but do you handle the case correctly when tz == sz? Also, ensure that you handle the case where t and s are identical.
Code Cleanliness:
There are many commented-out lines and unused includes, which might not cause functional issues but can make the code harder to read and maintain. Cleaning up the code can help you and others understand it better and may help you spot mistakes.
By focusing on these specific parts of the code, you may find the reason why it’s not producing the correct results or why it’s not passing the time constraints. Good luck with debugging!
Я не смог понять, что именно ведет к ошибке в твоем случае, но когда менял модули и основания хешей, почему-то сильно скакало кол-во пройденных тестов.
Это не совсем нормально, по идее если модуль и основание остаются взаимопростыми, то код должен валиться на одном и том же тесте.
Еще есть вариант написать двойные хеши, возможно ввиду кол-ва перебираемых тобой вариантов строки возникают многочисленные коллизии, и тесты валятся, так что попробуй
@Anton, I’ll examine the code and point out specific lines that could be problematic:
Line with ig Calculation:
The line where ig is calculated looks overly complex and is potentially incorrect due to excessive modulo operations and additions:
The subtraction and multiplication should also be modded separately to avoid negative values:
ll res = (h[i+tz-1] - (h[i-1]*x[tz])%mod + mod) % mod;
Using bool Vector for Hashes:
You are using a vector<bool> to store the hashes, which is indexed by the hash value itself:
vector <bool> mp(mod);
//...
mp[res]=1;
This is potentially problematic because hash collisions can occur, and there might be multiple strings with the same hash value. Using a vector indexed by the hash may not be the best approach. Consider using an unordered_map with the hash as the key and the starting positions as values.
Handling of Upper and Lowercase Characters:
When you calculate the hash values for all possible single-character modifications, you’re adding both lowercase and uppercase characters. Ensure that this is intended and correctly matches the problem statement.
Potential Array Out-of-Bounds Access:
Be cautious with array indices. For example, here:
ll x[sz+3];
You’re declaring x with sz+3 elements, but in the loop, you’re iterating up to sz:
for (int i=1; i<=sz; i++){
x[i]=x[i-1]*_x%mod;
}
Ensure that you’re not accessing x out of bounds in other parts of the code, especially if sz is close to the actual size of x.
By addressing these specific issues, you might be able to correct the bugs in your code. Remember to thoroughly test your code after each change to ensure that you’re moving in the right direction.
