안녕하세요, 10745번 문제를 aho-corasick으로 풀던 중 질문드립니다.

패턴의 길이가 총 m인 상태에서 밑 코드의 79번째 ~ 81번째 라인의 v.pop_back()을 실행하면

v의 capacity가 충분한 상황에서 time complexity가 O(m)이 될 것이라고 생각하고 있었습니다.

그런데 밑 코드를 제출하면 시간초과가 발생하게 되고 시간초과가 발생하는 데이터는

http://www.usaco.org/current/d...

의 14.in에서 발생합니다.

그래서 pop_back()을 주석 처리를 하고 실행시키면 빠르게 실행되는데 pop_back()만 살려놓으면 실행시간이 매우 느립니다.

그래서 궁금한 것은 저렇게 작성된 pop_back()의 총 time complexity가 궁금하고 코드를 어떻게 고치면 좋을지 힌트를 주시면 감사드리겠습니다.