http://mirror.codeforces.com/problemset/problem/182/D
this problem is tagged with hashing but i couldnt find any tutorial for it. can you please give me an idea for solving it by use of hashing? thanks.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.04.2026 15:36:06 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Solution: find all divisors of each string, and find common of them.
How to find all divisors? We know that divisor D is prefix of string S and |S| = 0 (mod |D|). So, amount of divisors is at maximum sqrt(|S|). Let's check all prefixes of string which length is <= sqrt(|S|) and check if we write this prefix |S| / |D| times it will be same as S. If it is, then prefix D is the divisor of S. How to check it? Check if substring [0, |T|) is same as [|T|, 2 * |T|) and [2 * |T|, 3 * |T|) and so on.. by using hash. Total time is |S| * sqrt(|S|). After, do the same to second string. You will have a two arrays of divisors of each string (the array of hashes). Then, you calculate how many divisors are common.
That's all.
ur wrong.
divisors (
.
aaaahasa,aa, andaaaa), butyes you are correct. can you suggest how to solve this?
Yes, he's wrong. there r no more 2 * sqrt(|S|) divisors. And, BTW, this problem can solved without using any string algorithm. See my solution. Sry for bad eng.
Omg, authors solution is really strange. We can find all divisors of the string in O(n) using Z-algorithm or KMP. Hashing can be used to compare divisors, but it could be simply done in naive way in O(n) totally for all divisors.
what do you mean by naive way? comparing all divisors char by char should be O(n^2), right?
Nope, it's not. 6729772
There are not that many divisors for a given N. So in fact the complexity is something around O(n4 / 3)
This discussion in Russian brings the estimate for cubic root: http://mirror.codeforces.com/blog/entry/651. You can google translate it or just read the links from it.
Pretty cool solution :D
All divisors are prefixes of the strings. So, we can check all common prefixes if they are divisors in both strings.
hey i am solving it with hashing but i am getting WA. same code gives correct answer on IDEONE http://ideone.com/1cv777 http://mirror.codeforces.com/contest/182/submission/6734760
someone please help me in debugging. i using lots of printfs but still i am unable to figure out the source of error. as i am yet to get AC on a hashing problem i dont feel very confident about it.
I have changed both
into
and it passed first three tests :D