Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4295299

Browse files
yuuurchykYurii A.adamant-pwn
authored
Manacher's algorithm testcases (#1393)
* Fix inconsistencies in Manacher's algorithm* Add test for manacher_odd* Update test_manacher_odd.cpp* empty commit to run tests?---------Co-authored-by: Yurii A. <l.soho@tuta.io>Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
1 parentb96e93b commit4295299

File tree

2 files changed

+78
-4
lines changed

2 files changed

+78
-4
lines changed

‎src/string/manacher.md

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ Such an algorithm is slow, it can calculate the answer only in $O(n^2)$.
4949
The implementation of the trivial algorithm is:
5050

5151
```cpp
52-
vector<int>manacher_odd(string s) {
52+
vector<int>manacher_odd_trivial(string s) {
5353
int n = s.size();
5454
s = "$" + s + "^";
5555
vector<int> p(n + 2);
@@ -68,7 +68,7 @@ Terminal characters `$` and `^` were used to avoid dealing with ends of the stri
6868
6969
We describe the algorithm to find all the sub-palindromes with odd length, i. e. to calculate $d_{odd}[]$.
7070
71-
For fast calculation we'll maintain the **borders $(l, r)$** of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is $s[l+1] s[l+2] \dots s[r-1]$). Initially we set $l = 0, r = 1$, which corresponds to the empty string.
71+
For fast calculation we'll maintain the **exclusiveborders $(l, r)$** of the rightmost found (sub-)palindrome (i. e. the current rightmost (sub-)palindrome is $s[l+1] s[l+2] \dots s[r-1]$). Initially we set $l = 0, r = 1$, which corresponds to the empty string.
7272
7373
So, we want to calculate $d_{odd}[i]$ for the next $i$, and all the previous values in $d_{odd}[]$ have been already calculated. We do the following:
7474
@@ -140,12 +140,12 @@ For calculating $d_{odd}[]$, we get the following code. Things to note:
140140
- The while loop denotes the trivial algorithm. We launch it irrespective of the value of $k$.
141141
- If the size of palindrome centered at $i$ is $x$, then $d_{odd}[i]$ stores $\frac{x+1}{2}$.
142142
143-
```cpp
143+
```{.cpp file=manacher_odd}
144144
vector<int> manacher_odd(string s) {
145145
int n = s.size();
146146
s = "$" + s + "^";
147147
vector<int> p(n + 2);
148-
int l =1, r = 1;
148+
int l =0, r = 1;
149149
for(int i = 1; i <= n; i++) {
150150
p[i] = max(0, min(r - i, p[l + (r - i)]));
151151
while(s[i - p[i]] == s[i + p[i]]) {

‎test/test_manacher_odd.cpp

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
#include<bits/stdc++.h>
2+
usingnamespacestd;
3+
4+
#include"manacher_odd.h"
5+
6+
stringgetRandomString(size_t n,uint32_t seed,char minLetter='a',char maxLetter='b') {
7+
assert(minLetter <= maxLetter);
8+
constsize_t nLetters =static_cast<int>(maxLetter) -static_cast<int>(minLetter) +1;
9+
std::uniform_int_distribution<size_t>distr(0, nLetters -1);
10+
std::mt19937gen(seed);
11+
12+
string res;
13+
res.reserve(n);
14+
15+
for (size_t i =0; i < n; ++i)
16+
res.push_back('a' +distr(gen));
17+
18+
return res;
19+
}
20+
21+
booltestManacherOdd(const std::string &s) {
22+
constauto n = s.size();
23+
constauto d_odd =manacher_odd(s);
24+
25+
if (d_odd.size() != n)
26+
returnfalse;
27+
28+
constauto inRange = [&](size_t idx) {
29+
return idx >=0 && idx < n;
30+
};
31+
32+
for (size_t i =0; i < n; ++i) {
33+
if (d_odd[i] <0)
34+
returnfalse;
35+
for (int d =0; d < d_odd[i]; ++d) {
36+
constauto idx1 = i - d;
37+
constauto idx2 = i + d;
38+
39+
if (!inRange(idx1) || !inRange(idx2))
40+
returnfalse;
41+
if (s[idx1] != s[idx2])
42+
returnfalse;
43+
}
44+
45+
constauto idx1 = i - d_odd[i];
46+
constauto idx2 = i + d_odd[i];
47+
if (inRange(idx1) &&inRange(idx2) && s[idx1] == s[idx2])
48+
returnfalse;
49+
}
50+
51+
returntrue;
52+
}
53+
54+
intmain() {
55+
vector<string> testCases;
56+
57+
testCases.push_back("");
58+
for (size_t i =1; i <=25; ++i) {
59+
auto s = string{};
60+
s.resize(i,'a');
61+
testCases.push_back(move(s));
62+
}
63+
testCases.push_back("abba");
64+
testCases.push_back("abccbaasd");
65+
for (size_t n =9; n <=100; n +=10)
66+
testCases.push_back(getRandomString(n,/* seed*/ n,'a','d'));
67+
for (size_t n =7; n <=100; n +=10)
68+
testCases.push_back(getRandomString(n,/* seed*/ n));
69+
70+
for (constauto &s: testCases)
71+
assert(testManacherOdd(s));
72+
73+
return0;
74+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp