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

Manacher's algorithm inconsistency#1393

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Conversation

yuuurchyk
Copy link
Contributor

Changes

  • fix a small inconsistency in Manacher's algorithm notation for the border of rightmost segment
  • write unittest to make sure the implementation remains correct

@yuuurchyk
Copy link
ContributorAuthor

yuuurchyk commentedNov 14, 2024
edited
Loading

Questions to Maintainers

Hey! Maybe I've missed it while reading contribution docs, but is there an ability to run tests locally (especially on OS other than unix)? I've been trying to useact tool, but it does not seem to work well (some errors in containers as well as file encoding problems). It may be helpful to be able to run tests locally before submitting the PR.

Also, couple of questions regarding tests:

  1. what about using cmake/some unittest framework?
  2. what about providing some docker container for the ability to launch tests locally? Is it on your list? (I may be able to help)

P.S. same question about providing docker container to render/display the docs locally

@yuuurchykyuuurchyk changed the titleFeature/manachers algorithm improvementsManacher's algorithm inconsistenciesNov 14, 2024
@yuuurchyk
Copy link
ContributorAuthor

Also, what about adding this problem to the list?https://leetcode.com/problems/longest-palindromic-substring/description/

@yuuurchykyuuurchyk changed the titleManacher's algorithm inconsistenciesManacher's algorithm inconsistencyNov 14, 2024
@jxu
Copy link
Contributor

jxu commentedNov 14, 2024
edited
Loading

Idk what act tool is. Are you on windows or Mac? with windows you should be able to run on WSL and on Mac you can get a more recent version of bash to run test.sh. The checks are run manually but can probably be set to run automatically.

yuuurchyk reacted with thumbs up emoji

@yuuurchyk
Copy link
ContributorAuthor

@jxu thanks for the info. I'm on win. For some reason, I didn't think about WSL, but rather was trying to launch the container specified in github actions locally on my machine :)
I will try using WSL next time

@jxu
Copy link
Contributor

jxu commentedNov 15, 2024

The container approach should work too as long as you have a standard bash, python, and C++ compiler environment set up

@adamant-pwn
Copy link
Member

Hi there! You can run tests locally via bash script, as describedhere. I think in the long run it'd be great to somehow integrate code snippets withhttps://lib.cp-algorithms.com, but I'm not really sure how it can be done, if at all.

As for Docker, etc, I don't think we have the capacity to develop something on our end for this. That is, if someone comes up with a solution that somehow makes our life easier, we'd be happy to discuss it over a pull request.

#include <bits/stdc++.h>
using namespace std;

#include "manacher_odd.h"
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Could you also add a test onvector<int> manacher(string s), please?

Copy link
Member

@adamant-pwnadamant-pwn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Thanks for the pull request! If it is okay for you, could you also covermanacher with tests? I think it should be a minimal change in the current context.

Copy link
Member

@adamant-pwnadamant-pwn left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Actually, let me merge this first to fixate the progress. But I would appreciate it if you add a test formanacher in a separate pull request.

@adamant-pwnadamant-pwn merged commit4295299 intocp-algorithms:mainMar 24, 2025
3 checks passed
github-actionsbot added a commit that referenced this pull requestMar 24, 2025
Bhaskar1312 pushed a commit to Bhaskar1312/cp-algorithms that referenced this pull requestApr 19, 2025
* 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>
@yuuurchykyuuurchyk deleted the feature/manachers-algorithm-improvements branchMay 23, 2025 23:12
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@adamant-pwnadamant-pwnadamant-pwn approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

3 participants
@yuuurchyk@jxu@adamant-pwn

[8]ページ先頭

©2009-2025 Movatter.jp