**[Problem]**: [problem:1200E]↵
**[Solution]**: [submission:74203908]↵
↵
I'm getting a TLE on test 3. I'm using hashing to answer queries "Is string A equal to string B?" in O(1) time with O(N) preprocessing time. I'm doing N queries at worst so my time complexity should be O(N + N) = O(N).↵
↵
As I'm just learning hashing I was using this solution([submission:58603158]) to check if I'm doing the right things. The only difference in the two solution should be(I might have overlooked something, if that's the case I'm sorry) that I'm using two-dimensional arrays to save the two hashes per prefix, where the other solution is using vectors. The other difference is that instead of using modular multiplicative inverse to "divide" the hash of the substring I'm querying for and "drag" it such that there are 0 empty spaces before it, I'm multiplying so that I "push" the substring to the end so that there are MAXN(1e6 + 5 in my code) empty spaces.↵
↵
↵
Let's say in string "abcdefg", I'm querying for substring from index 4 to 6 (0-indexex):↵
1) I will subtract the hash of prefix "abcd" from prefix "abcdefg". The result will be "____efg"(_ is a empty space, 0 value);↵
2) Instead of "dragging" the substring I'm querying for so that I get the hash for "efg", I multiply it so that I get MAXN(1e6 + 5 in my code) empty spaces "_" and "efg" at the end.↵
↵
I hope that made my idea more clear.↵
↵
Thanks in advance for the help!↵
↵
UPD1: I and a friend of mine tried some optimizations and found that the f() function was not working properly(it returned the same values for 'X' and 'x') but I still get TLE on test 3.
**[Solution]**: [submission:74203908]↵
↵
I'm getting a TLE on test 3. I'm using hashing to answer queries "Is string A equal to string B?" in O(1) time with O(N) preprocessing time. I'm doing N queries at worst so my time complexity should be O(N + N) = O(N).↵
↵
As I'm just learning hashing I was using this solution([submission:58603158]) to check if I'm doing the right things. The only difference in the two solution should be(I might have overlooked something, if that's the case I'm sorry) that I'm using two-dimensional arrays to save the two hashes per prefix, where the other solution is using vectors. The other difference is that instead of using modular multiplicative inverse to "divide" the hash of the substring I'm querying for and "drag" it such that there are 0 empty spaces before it, I'm multiplying so that I "push" the substring to the end so that there are MAXN(1e6 + 5 in my code) empty spaces.↵
↵
↵
Let's say in string "abcdefg", I'm querying for substring from index 4 to 6 (0-indexex):↵
1) I will subtract the hash of prefix "abcd" from prefix "abcdefg". The result will be "____efg"(_ is a empty space, 0 value);↵
2) Instead of "dragging" the substring I'm querying for so that I get the hash for "efg", I multiply it so that I get MAXN(1e6 + 5 in my code) empty spaces "_" and "efg" at the end.↵
↵
I hope that made my idea more clear.↵
↵
Thanks in advance for the help!↵
↵
UPD1: I and a friend of mine tried some optimizations and found that the f() function was not working properly(it returned the same values for 'X' and 'x') but I still get TLE on test 3.
