I was thinking in terms of finding all subgraph isomorphisms. But this definitely is O(N) if all you need is one solution.
But then I thought about it even further and this reduces to sliding window problem. In this case you still need to travel to each node in the window to see if there’s a match.
So it cannot be that you traverse each node once. Not if you want to find all possible subgraph isomorphisms.
Imagine a string that is a fractal of substrings:
rrrrrrrrrrrrrrrrrrrrrrrrrrrr
And the other one:
rrrrrrr
Right? The sliding window for rrrrrrr will be 7 in length and you need to traverse that entire window every time you move it. So by that fact alone every node is traversed at least 7 times.
I was thinking in terms of finding all subgraph isomorphisms. But this definitely is O(N) if all you need is one solution.
But then I thought about it even further and this reduces to sliding window problem. In this case you still need to travel to each node in the window to see if there’s a match.
So it cannot be that you traverse each node once. Not if you want to find all possible subgraph isomorphisms.
Imagine a string that is a fractal of substrings:
And the other one: Right? The sliding window for rrrrrrr will be 7 in length and you need to traverse that entire window every time you move it. So by that fact alone every node is traversed at least 7 times.