阅读程序（3）

13-18题   组合题

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串，若x＞y则s[x…y]是空串。t[x…y]同理。

#include 

#include 

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=o; i＜=slen; ++i）{

while（j＜=slen && tmp ＞=suf[j] + 1） ++j；

ans =max(ans, j – I – 1);

tmp = pre[i];

}

cout ＜＜ans ＜＜ end1;

return 0;

}

提示：

t[0…pre[i]-1]是s[0…i]的子序列；

t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。

程序输出时，suf数组满足：对任意0≤i＜slen，suf[i] ≤suf[i+1]。( )