### Example Patterns for Teddy Algorithm

Source: https://github.com/burntsushi/aho-corasick/blob/master/src/packed/teddy/README.md

These are the example patterns used to illustrate the Teddy algorithm's fingerprinting mechanism.

```ignore
foo
bar
baz
```

--------------------------------

### Fingerprint Mapping Example

Source: https://github.com/burntsushi/aho-corasick/blob/master/src/packed/teddy/README.md

Illustrates how single-byte fingerprints are mapped to patterns in the Teddy algorithm.

```ignore
f |--> foo
b |--> bar, baz
```

--------------------------------

### Example Haystack Block for Teddy Algorithm

Source: https://github.com/burntsushi/aho-corasick/blob/master/src/packed/teddy/README.md

This is an example 16-byte block from the haystack used to demonstrate Teddy's scanning process.

```ignore
bat cat foo bump
xxxxxxxxxxxxxxxx
```

--------------------------------

### SIMD Vector A Example for Teddy Algorithm

Source: https://github.com/burntsushi/aho-corasick/blob/master/src/packed/teddy/README.md

An example of a SIMD vector 'A' containing bitmasks used in conjunction with the PSHUFB instruction for fingerprint lookups.

```ignore
    0x00 0x01 ... 0x62      ... 0x66      ... 0xFF
A = 0    0        00000110      00000001      0
```

--------------------------------

### SIMD Vector Transformation Example (PSHUFB)

Source: https://github.com/burntsushi/aho-corasick/blob/master/src/packed/teddy/README.md

Illustrates the transformation of byte arrays (B0, B1) using the PSHUFB instruction to index into other arrays (A0, A1) for pattern matching. This is a key step in optimizing the algorithm with SIMD.

```ignore
     b   a   t   _   c   a   t   _   f   o   o   _   b   u   m   p
B0 = 0x2 0x1 0x4 0x0 0x3 0x1 0x4 0x0 0x6 0xF 0xF 0x0 0x2 0x5 0xD 0x0
B1 = 0x6 0x6 0x7 0x2 0x6 0x6 0x7 0x2 0x6 0x6 0x6 0x2 0x6 0x7 0x6 0x7
```

```ignore
     b         a        ... f         o         ... p
     A0[0x2]   A0[0x1]      A0[0x6]   A0[0xF]       A0[0x0]
C0 = 00000110  0            00000001  0             0
```

```ignore
     b         a        ... f         o        ... p
     A1[0x6]   A1[0x6]      A1[0x6]   A1[0x6]      A1[0x7]
C1 = 00000111  00000111     00000111  00000111     0
```

```ignore
     b         a        ... f         o        ... p
C  = 00000110  0            00000001  0            0
```

--------------------------------

### Checking for Prefix Matches

Source: https://github.com/burntsushi/aho-corasick/blob/master/DESIGN.md

Demonstrates how to check if a haystack starts with any of the patterns stored in a trie. It traverses the trie based on the haystack's bytes, returning true if a match state is reached.

```rust
fn has_prefix(trie: &Trie, haystack: &[u8]) -> bool {
  let mut state_id = trie.start();
  // If the empty pattern is in trie, then state_id is a match state.
  if trie.is_match(state_id) {
    return true;
  }
  for (i, &b) in haystack.iter().enumerate() {
    state_id = match trie.next_state(state_id, b) {
      Some(id) => id,
      // If there was no transition for this state and byte, then we know
      // the haystack does not start with one of the patterns in our trie.
      None => return false,
    };
    if trie.is_match(state_id) {
      return true;
    }
  }
  false
}
```

--------------------------------

### Basic multi-pattern search

Source: https://github.com/burntsushi/aho-corasick/blob/master/README.md

Demonstrates searching for multiple patterns within a text and retrieving the matched pattern ID and byte offsets. Ensure patterns are provided as a slice of strings.

```rust
use aho_corasick::{AhoCorasick, PatternID};

let patterns = &["apple", "maple", "Snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";

let ac = AhoCorasick::new(patterns).unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
    matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
    (PatternID::must(1), 13, 18),
    (PatternID::must(0), 28, 33),
    (PatternID::must(2), 43, 50),
]);
```

--------------------------------

### Get Aho-Corasick Automaton Statistics

Source: https://context7.com/burntsushi/aho-corasick/llms.txt

Retrieve the number of patterns, minimum pattern length, and maximum pattern length from a built Aho-Corasick automaton. This is useful for understanding the scale of the patterns indexed.

```rust
use aho_corasick::AhoCorasick;

let ac = AhoCorasick::new(&["foo", "bar", "quux", "baz"]).unwrap();

// Get pattern statistics
assert_eq!(4, ac.patterns_len());
assert_eq!(3, ac.min_pattern_len());
assert_eq!(4, ac.max_pattern_len());

// Check memory usage for capacity planning
let memory = ac.memory_usage();
println!("Automaton uses {} bytes", memory);

// Query match and start configuration
println!("Match kind: {:?}", ac.match_kind());
println!("Start kind: {:?}", ac.start_kind());
```

--------------------------------

### Leftmost-First Aho-Corasick Match

Source: https://github.com/burntsushi/aho-corasick/blob/master/README.md

Configures the Aho-Corasick algorithm to use leftmost-first match semantics, similar to Perl-like regular expressions, ensuring the longest possible match starting at the earliest position is found.

```rust
use aho_corasick::{
    AhoCorasick,
    MatchKind
};

let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";

let ac = AhoCorasick::builder()
    .match_kind(MatchKind::LeftmostFirst)
    .build(patterns)
    .unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
```

--------------------------------

### DFA Search Implementation

Source: https://github.com/burntsushi/aho-corasick/blob/master/DESIGN.md

This code demonstrates the search logic for a Deterministic Finite Automaton (DFA). It iterates through the input, transitioning between states based on each byte, and returns true if a match state is reached. This implementation is optimized for speed due to its single-state-at-a-time transitions.

```rust
fn contains(dfa: &DFA, haystack: &[u8]) -> bool {
  let mut state_id = dfa.start();
  // If the empty pattern is in dfa, then state_id is a match state.
  if dfa.is_match(state_id) {
    return true;
  }
  for (i, &b) in haystack.iter().enumerate() {
    // An Aho-Corasick DFA *never* has a missing state that requires
    // failure transitions to be followed. One byte of input advances the
    // automaton by one state. Always.
    state_id = dfa.next_state(state_id, b);
    if dfa.is_match(state_id) {
      return true;
    }
  }
  false
}
```

--------------------------------

### Optimized DFA Transition Calculation with Premultiplication

Source: https://github.com/burntsushi/aho-corasick/blob/master/DESIGN.md

This optimized method for computing the next state ID in a DFA leverages premultiplied state identifiers, reducing a multiplication to an addition.

```rust
next_state_id = dfa.transitions[current_state_id + current_byte]
```

--------------------------------

### Nybble-Based Bitset Masks and Haystack Block

Source: https://github.com/burntsushi/aho-corasick/blob/master/src/packed/teddy/README.md

Demonstrates the use of two nybble masks (A0, A1) and a haystack block (B) for SIMD-based fingerprint matching in the Teddy algorithm.

```ignore
      0x00 0x01 0x02      0x03 ... 0x06      ... 0xF
A0 =  0    0    00000110  0        00000001      0
A1 =  0    0    0         0        00000111      0
B  =  b    a    t         _        t             p
B  =  0x62 0x61 0x74      0x20     0x74          0x70
```