I have solved the easy version of the problem. But I have no idea how to solve this one. Do I require any new algorithms? Can someone please help me solve this problem?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | nor | 155 |
| 7 | adamant | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.09.2024 22:53:36 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by negetive_iq (previous revision, new revision, compare).
Learn pattern searching algorithms like Z function, KMP, etc. I used Z function to solve this question.
Can you explain a bit more in detail on how to solve this after learning pattern matching algorithms?
The problem after this will turn into "for string $$$s$$$ of length $$$n$$$, find any index $$$i$$$ ($$$2 \le i \le n$$$) such as $$$s(i, n) = s(1, n-i+1)$$$ and $$$i \le n-i+1$$$".
(Here, $$$s(i, j)$$$ means a contiguous substring of $$$s$$$ from index $$$i$$$ to index $$$j$$$, inclusively).
Thanks!
Can you give me the link to the problem?
https://codeforces.net/problemset/problem/2010/C1
To solve the problem, analyze the string
tto determine if it can be the result of merging two identical consecutive messages. Compute the length of the longest prefix that is also a suffix of the string. If this length is at least half the length oftplus one, it indicates a possible merging error, and you should print "YES" along with the prefix. If not, print "NO". For this, you can use the KMP algorithm’s LPS (Longest Prefix Suffix) array to efficiently find the longest prefix which is also a suffix.