두 개의 소문자 문자열 s와 t가 있다고 가정하면 t와 동일한 s의 부분 시퀀스 수를 찾아야 합니다. 답이 매우 크면 10^9 + 7로 결과를 반환합니다.
따라서 입력이 s ="abbd" t ="bd"와 같으면 두 개의 가능한 하위 시퀀스 "bd"가 있으므로 출력은 2가 됩니다.
-
s[1] s[3] 연결
-
s[2] s[3]을 연결합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=10^9 + 7
-
t의 크기가 0과 같으면 -
-
0 반환
-
-
t가 s와 같으면 -
-
1 반환
-
-
t의 크기> s의 크기인 경우 -
-
0 반환
-
-
t + 1의 크기와 동일한 크기의 배열 테이블을 정의하고 0으로 채움
-
테이블[0] :=1
-
initialize i :=0의 경우, i
-
onsave 배열 정의 :=table
-
j 초기화의 경우:=0, j <테이블 크기일 때 업데이트(j를 1만큼 증가), −
-
s[i]가 t[j]와 같으면 -
-
테이블[j + 1] =(테이블[j + 1] mod m + onsave[j] mod m)
-
-
-
-
테이블[j + 1] =(테이블[j + 1] mod m + onsave[j] mod m)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
int solve(string s, string t) {
int m = 1000000007;
if (t.size() == 0)
return 0;
if (t == s)
return 1;
if (t.size() > s.size())
return 0;
vector<int> table(t.size() + 1, 0);
table[0] = 1;
for (int i = 0; i < s.size(); i++) {
vector<int> onsave = table;
for (int j = 0; j < table.size(); j++) {
if (s[i] == t[j]) {
table[j + 1] = (table[j + 1] % m + onsave[j] % m) %m;
}
}
}
return table[t.size()] % m;
}
main(){
string s = "abbd", t = "bd";
cout << (solve(s, t));
} 입력
"abbd", "bd"
출력
2