두개의 스트링이 주어졌을 떄, 불연속적인 섭스트링의 갯수를 구해라

ex) "cat", "catapult"

>> "CATapult", "CatApulT", "CAtapulT"

답 : 3

솔루션 : 우선 바로 떠오르는 방법은 없으니 나이브에서 시작하자. DP로 비벼지는게 보인다 O(MN)으로.

int findall(string & s, string & t, int scurr, int tcurr){

if(tcurr==t.size()) return 1;

// go through starting from scurr

int ret = 0;

for(int i = scurr ; i<s.size() ; i++){

if(s[i]==t[tcurr]){

ret += findall(s,t,i+1,tcurr+1);

}

}

return ret;

}

캐싱을 적용하면 O(MN)으로 하드캐핑 된다. 그리고 내부 시간 복잡도는 최악의 경우 N에 비례하므로 결국 O(MN^2) 정도가 되지 않을까.