t 是 s 的子序列的意思是:从 s 中删去若干个字符,可以得到 t;特别的,如果 s=t,那么 t 也是 s 的子序列;空串是任何串的子序列。例如:acd 是 abcde 的子序列,acd是 acd的子序列,但 adc不是 abcde 的子序列。
s[x..y] 表示 s[x]⋯s[y]共 y−x+l个字符构成的字符串,若 x>y则 s[x..y]是空串。t[x..y]同理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <iostream> #include <string> using namespace std; const int max1 = 202; string s, t; int pre[max1], suf[max1]; int main() { cin >> s >> t; int slen = s.length(), tlen = t.length(); for (int i = 0, j = 0; i < slen; ++i) { if (j < tlen && s[i] == t[j]) ++j; pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列 } for (int i = slen - 1 , j = tlen - 1; i >= 0; --i) { if(j >= 0 && s[i] == t [j]) --j; suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列 } suf[slen] = tlen -1; int ans = 0; for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){ while(j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; } |
提示:
t[0…pre[i]−1]是 s[0…i]的子序列;
t[suf[i]+1…tlen−1]是 s[i…slen−1]的子序列。
0 of 6 Questions completed
Questions:
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
0 of 6 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0)
0 Essay(s) Pending (Possible Point(s): 0)
1、程序输出时,suf
数组满足:对任意 0≤i<slen, suf[i]≤suf[i+1]。
2、当t是s的子序列时,输出一定不为 0。
3、程序运行到第23 行时,j−i−1一定不小于 0。
4、当 t 是 s 的子序列时,pre
数组和 suf
数组满足:对任意 0≤i<slen, pre[i]>suf[i+1]+1 。
5、若 tlen=10
,输出为 0,则 slen 最小为( )。
6、若 tlen=10
,输出为 2,则 slen最小为( )。