string-algorithm-matcher
Scannednpx machina-cli add skill a5c-ai/babysitter/string-algorithm-matcher --openclawFiles (1)
SKILL.md
2.0 KB
String Algorithm Matcher Skill
Purpose
Match string processing problems to the most appropriate algorithms based on requirements and constraints.
Capabilities
- Pattern matching algorithm selection (KMP, Z, Rabin-Karp)
- Suffix structure selection (array vs tree vs automaton)
- Palindrome detection algorithm selection
- Rolling hash implementation guidance
- String DP technique matching
Target Processes
- pattern-matching-algorithms
- trie-suffix-structures
- string-processing
Algorithm Selection Guide
Single Pattern Matching
| Scenario | Algorithm | Complexity |
|---|---|---|
| Single pattern | KMP | O(n+m) |
| Multiple patterns | Aho-Corasick | O(n+m+z) |
| Approximate match | Rolling Hash | O(n*m) average |
Suffix Structures
| Need | Structure | Build Time |
|---|---|---|
| Substring search | Suffix Array | O(n log n) |
| Multiple queries | Suffix Tree | O(n) |
| Subsequence counting | Suffix Automaton | O(n) |
Palindromes
| Problem | Algorithm |
|---|---|
| Longest palindromic substring | Manacher |
| Palindrome partitioning | DP + Manacher |
| Palindrome queries | Hashing |
Input Schema
{
"type": "object",
"properties": {
"problemDescription": { "type": "string" },
"problemType": {
"type": "string",
"enum": ["patternMatch", "suffixQueries", "palindrome", "subsequence", "dp"]
},
"constraints": { "type": "object" }
},
"required": ["problemDescription"]
}
Output Schema
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"algorithm": { "type": "string" },
"complexity": { "type": "string" },
"alternatives": { "type": "array" },
"implementation": { "type": "string" }
},
"required": ["success", "algorithm"]
}
Source
git clone https://github.com/a5c-ai/babysitter/blob/main/plugins/babysitter/skills/babysit/process/specializations/algorithms-optimization/skills/string-algorithm-matcher/SKILL.mdView on GitHub Overview
This skill maps string processing tasks to the most effective algorithms. It covers pattern matching, suffix structures, palindrome detection, rolling hash, and string DP, guiding selection based on requirements and constraints.
How This Skill Works
It analyzes the input problem description and constraints, then uses the Algorithm Selection Guide to pick the right algorithm and data structure. It outputs a recommended algorithm, expected complexity, alternatives, and implementation guidance to align with the task at hand.
When to Use It
- Pattern matching problems: choose KMP for a single pattern, or Aho-Corasick for multiple patterns.
- Suffix-structure needs: use Suffix Array for substring search, Suffix Tree for multiple queries, or Suffix Automaton for subsequence counting.
- Palindrome-related tasks: apply Manacher for longest palindromic substrings or combine DP with Manacher for partitions.
- Approximate or flexible matching: consider Rolling Hash for probabilistic or average-case efficiency.
- DP-based or hashing-based string solutions: map to string DP techniques when dynamic programming or hashing simplifies the problem.
Quick Start
- Step 1: Describe the problem and constraints clearly.
- Step 2: Select the algorithm family from the guide (pattern, suffix, palindrome, rolling hash, or DP).
- Step 3: Implement with the recommended data structures and validate edge cases.
Best Practices
- Clearly articulate the problem description and constraints before selecting an algorithm.
- Reference the Algorithm Selection Guide to map scenarios to algorithm families (pattern matching, suffix structures, palindrome, rolling hash, DP).
- Assess time and space complexity against input sizes and expected workload.
- Choose data structures (suffix array, suffix tree, suffix automaton) when multiple queries or subsequence counting are needed.
- Validate edge cases (empty strings, overlapping patterns, and multiple patterns) with representative tests.
Example Use Cases
- Find a single keyword in a large text using KMP for linear-time pattern matching.
- Detect multiple keywords efficiently with Aho-Corasick in streaming logs.
- Perform substring search across a large corpus using a Suffix Array.
- Compute the longest palindromic substring with Manacher.
- Use Rolling Hash for approximate matches or document similarity checks.
Frequently Asked Questions
Add this skill to your agents
