- This C# app was created by Team Jajarija, consisting of Angie, Nuel, and Amel, as part of our third major assignment for the Algorithm Strategies course. The app implements the Boyer Moore and Knuth-Morris-Pratt (KMP) algorithm to find the best match of an altered fingerprint image from some databases. We hope you enjoy exploring it!
- Knuth-Morris-Pratt (KMP)
- Boyer Moore (BM)
- Regular Expression
- Technologies Used
- Program Requirement
- Steps to Run
- Preview
- Author
To locate patterns in a text, one effective string searching method is the Knuth-Morris-Pratt (KMP) algorithm. In order to prevent unnecessary comparisons of characters that are already known to match or mismatch, it makes use of information from the pattern itself. When a mismatch occurs, KMP creates a "prefix function" table that assists in ignoring a certain number of characters in the text, hence lowering the overall number of comparisons required. The KMP algorithm has an O(N + M) time complexity, where N is the text's length and M is the pattern's length.
The Boyer-Moore (BM) algorithm is a highly efficient string searching algorithm used to find occurrences of a pattern within a text. It works by preprocessing the pattern to create two heuristics: the bad character rule and the good suffix rule. The bad character rule allows the algorithm to skip sections of the text based on the presence of mismatched characters, while the good suffix rule allows it to skip sections based on matching suffixes of the pattern. This enables BM to skip large portions of the text, making it particularly fast for large alphabets. The best-case time complexity of BM is O(N/M), while the worst-case time complexity is O(N * M), where N is the length of the text and M is the length of the pattern.
To handle the alay version in this assignment, we use a series of regular expressions in the AlayMatcher class. First, both the original and alay strings are converted to lowercase to ensure case insensitivity. Second, all spaces are removed from both strings. Third, vowels in the original string are made optional using regex patterns, allowing for their absence in the alay string. Fourth, specific characters in the original string are replaced with regex patterns to account for common alay substitutions, such as 'a' being replaced by '[a@4]' and 'i' by '[i1!]'. Fifth, a regex pattern is constructed from the modified original string. Finally, this pattern is used to check if the alay string matches, ensuring that common transformations in alay writing are accurately captured.
- Avalonia - version 11.0.10
- Mariadb - version 11 +
- .NET - version 8.0
- MySql.Data version 8.4.0
- DotNetEnv - version 3.0.0
- C#
- Avalonia
- .NET
Before running, make sure to make the database first in your local database using any sqldump and have all the nessecary requirement installed.
git clone https://github.com/angiekierra/Tubes3_jajarija.git
cd TUBES3_Jajarija
Use the following format for your .env
DB_HOST=localhost
DB_USER=root
DB_PASSWORD=<yourdatabasepassword>
DB_DATABASE=<yourdatabasename>
cd Converter
dotnet run
// Navigate to src directory
cd ../src
dotnet restore
dotnet build
dotnet run
Created by:
Name | NIM | Contact | Github |
---|---|---|---|
Amalia Putri | 13522042 | [email protected] | amaliap21 |
Angelica Kierra Ninta Gurning | 13522048 | [email protected] | angiekierra |
Imanuel Sebastian Girsang | 13522058 | [email protected] | ImanuelSG |