题目：求两组字符串中最大的按顺序出现的同样单词数目。
分析：dp。最大公共子序列（LCS）。
把单词整个看成一个元素比較就可以。
状态：f（i，j）为s1串前i个单词与s2串前j个单词的最大匹配数；
转移：f（i，j）= max（f（i-1，j），f（i。j-1））{ s1[i] ≠ s2[j] }；
f（i-1，j-1）+ 1。
这里的字母包含数字
说明：数据输入。须要先分解成单词，然后计算就可以。
#include#include #include #include using namespace std;char buf[1001]; char s1[1001][22];char s2[1001][22];int f[1001][1001];int letter(char c){ if (c >= 'a' && c <= 'z') return 1; if (c >= 'A' && c <= 'Z') return 1; if (c >= '0' && c <= '9') return 1; return 0;}int getword(char s[][22], char *t){ int move = 0,count = 0; while (t[move]) { while (t[move] && !letter(t[move])) move ++; if (!t[move]) break; int now = move; while (letter(t[move])) move ++; int save = 0; while (now < move) s[count][save ++] = t[now ++]; s[count][save] = 0; count ++; } return count;}int main(){ int blank = 0,l1,l2,cases = 1; while (gets(buf)) { if (!strlen(buf)) blank = 1; l1 = getword(s1, buf); gets(buf); if (!strlen(buf)) blank = 1; l2 = getword(s2, buf); printf("%2d. ",cases ++); if (blank) { printf("Blank!\n"); blank = 0; }else { for (int i = 0 ; i <= l1 ; ++ i) for (int j = 0 ; j <= l2 ; ++ j) f[i][j] = 0; for (int i = 1 ; i <= l1 ; ++ i) for (int j = 1 ; j <= l2 ; ++ j) { f[i][j] = f[i-1][j]; if (f[i][j] < f[i][j-1]) f[i][j] = f[i][j-1]; if (!strcmp(s1[i-1], s2[j-1])) f[i][j] = f[i-1][j-1]+1; } printf("Length of longest match: %d\n",f[l1][l2]); } } return 0;}