algorithm - DFS in DFS, DFS with a known string -

i looking complexity calculation of code. dfs(depth first search) in dfs. dfs runs on graph (state machine) end start (backward search). whenever reaches start, accumulates string made reach start , tries string on graph dfs check if reaches start state on other graph same string.

the outer dfs complexity definetely o(vo+eo) vo : number of vertex in outer graph , eo : number of edges in outer graph. what's complexity of inside dfs when string followed known?

and if possible, can answer whole complexity of algorithm?

i not sure whether o((eo+vo)+(ei+vi)) or o((eo+vo)(ei+vi)) or smtg .else

thank in advance,

it depends on in case second dfs fails. failing mean tells second graph not contain string found in first dfs.

if second dfs failing means backtrack , search string in first dfs , try second dfs again, complexity o((eo+vo)*(ei+vi)) because may in worst case full dfs of second graph every single dfs path start node in first dfs.

if second dfs failing means stop, @ worst perform single dfs of first graph , single dfs of second graph giving o((eo+vo)+(ei+vi)) worst case complexity.

the fact dfsing check if graph contains string means in cases may able terminate dfs (for example reach non-start vertex no characters remaining check). however, whether able terminate depends entirely on structure of graph second dfs in worst case still o(ei+vi) because nasty graph may still find going through edges , vertices.