String

Publish on: 2025-08-18 Classify at: Leetcode

Words: 150 Read:≈ 1mins Views:

Pattern: abababzababab

Step 1: Construct next array while traversing pattern.

next[i] represents maximum common prefix-suffix length for s[0:i+1]
Initialize j=0, i traverses from 1 to n-1. j position indicates current common prefix-suffix s[:j]
During traversal, if common prefix-suffix exists, continuously compare s[i] and s[j]. If different, in loop backtrack j until s[:j] becomes common prefix-suffix. Backtrack to second longest common prefix-suffix, move j to next[j-1]
Compare s[i] and s[j] again. If same, move j and assign next[i]

Step 2: Compare two strings abeababeabf abeabf

i traverses string, j points to pattern. In each loop, j position indicates needle[0:j] matches string
When match exists, check haystack[i] and needle[j]. If different, backtrack j to next[j-1]
Compare haystack[i] and needle[j] again. If same, move j

Sort by frequency descending, fill even positions first, then odd positions