# UNDF: UNDF-2026-000000486
# opencv-0002: G-API pattern_matching — O(M×E) std::find on patternEndOpNodes/patternStartOpNodes inside match loop

## Location
`modules/gapi/src/compiler/passes/pattern_matching.cpp` lines 289–312
Repository: https://github.com/opencv/opencv

## Severity
**MEDIUM** — Called during G-API graph compilation when identifying kernel fusion patterns. With M matched nodes and E/S end/start op nodes in a pattern, each iteration of the matching loop does two O(E) and O(S) linear scans. For large compute graphs (video pipelines with many nodes), this is O(M×(E+S)) per pattern match attempt.

## Complexity
- Before: O(M × (E + S)) — two std::find calls inside the outer while loop over M matches
- After: O(M + E + S) — two unordered_set lookups after O(E+S) set construction

## Defective Code

```cpp
// pattern_matching.cpp:289-312
while (!stop) {
    for (std::size_t index = 0u; index < size && !stop; ++index, ++matchIt) {
        // O(E) linear scan inside loop over M matched nodes
        bool cond1 = std::find(patternEndOpNodes.begin(),
                               patternEndOpNodes.end(),
                               matchIt->first)
                     != patternEndOpNodes.end();
        if (cond1) {
            subgraphEndOps[matchIt->first] = matchIt->second;
        }

        // O(S) linear scan inside loop over M matched nodes
        bool cond2 = std::find(patternStartOpNodes.begin(),
                               patternStartOpNodes.end(),
                               matchIt->first)
                     != patternStartOpNodes.end();
        if (cond2) {
            subgraphStartOps[matchIt->first] = matchIt->second;
        }

        if (!cond1 && !cond2) {
            subgraphInternals.push_back(matchIt->second);
        }
        // ...
    }
}
```

**Problem:** `patternEndOpNodes` and `patternStartOpNodes` are vectors. Each `std::find`
call is O(E) and O(S) respectively. These searches happen inside a while loop over M
matched nodes, giving O(M×E + M×S) total.

## Fixed Code

```cpp
// Build O(1)-lookup sets before the loop
std::unordered_set<ade::NodeHandle> endOpSet(
    patternEndOpNodes.begin(), patternEndOpNodes.end());
std::unordered_set<ade::NodeHandle> startOpSet(
    patternStartOpNodes.begin(), patternStartOpNodes.end());

while (!stop) {
    for (std::size_t index = 0u; index < size && !stop; ++index, ++matchIt) {
        bool cond1 = endOpSet.count(matchIt->first) > 0;    // O(1)
        if (cond1) {
            subgraphEndOps[matchIt->first] = matchIt->second;
        }

        bool cond2 = startOpSet.count(matchIt->first) > 0;  // O(1)
        if (cond2) {
            subgraphStartOps[matchIt->first] = matchIt->second;
        }

        if (!cond1 && !cond2) {
            subgraphInternals.push_back(matchIt->second);
        }
        // ...
    }
}
```

## CWE
CWE-407: Inefficient Algorithmic Complexity — O(M×(E+S)) → O(M+E+S)
