bavernet/codejam-lib

A library implementing a variety of useful algorithms

codejam-lib's Issues

string: KMP algorithm

KMP (Knuth–Morris–Pratt Algorithm) is widely used for string comparison.
Because of the algorithm, we can use search words in many documents.
There are a lot of effective algorithms for string comparison, but this is simple and introduced in many articles or books.

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

graph: SPFA algorithm

SPFA(Shortest Path Faster Algorithm) is an algorithm used for shortest path and network flow.
It is from Bellman-Ford algorithm and it is optimized on updating edges with costs.
Thus, it can solve a shortest path problem with graphs which has edges with negative costs and it is better than Bellman-Ford in terms of average time complexity.

https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm

math: big integer implementation

Big integer structure is widely used.
But, there is no proper libraries for big integer in C/C++ languages.
If you can use the languages which support big integer structure internally, you should do that.
Or, you have to choose a library or to implement it.

For the unusual situation, it is needed to implement a big integer structure.

Add github action to test the repository right after pull requests

Github supports event-driven actions for CI/CD.
This repository has developed by TDD. It could be verified by testing the testcases right after pull requests.

add README.md

add readme file for first users

choose unit-test framework before implementing libraries

This repository would have a variety of useful libraries.
In order to make it possible to improve without errors, it needs a verification system.
Unit-test can be a solution to verify it.

graph: dijkstra algorithm

dijkstra algorithm is useful and commonly known for shortest path.
I think the algorithm is the most important one to solve graph search.

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm