Love letter<?xml:namespace prefix = o />

Time Limit: 1000MS? Memory Limit:10000K

?

【Description】

?

立哥最近收到一封情書，其字里行間那誠摯的內(nèi)心獨(dú)白和純真的感情敘述令立哥感動(dòng)不已。但已有4次被甩經(jīng)歷的立哥怎么也不明白為什么會(huì)有女孩子突然莫名其妙給自己寫情書。擁有超高智商的立哥很快想到這有可能是他的那幫狐朋狗友在捉弄他，所以在按照情書的約定于某月某日晚上12點(diǎn)半赴上海市郊黃渡鎮(zhèn)見面之前，立哥打算先暗中調(diào)查一下這封情書是不是他的那幫死黨炮制出來的。

他花了好大的功夫，終于把這幫人平時(shí)寫給女生們的怪詩以及他們的心情日記、檢討等搜集起來，匯總成冊（立哥將該冊子稱為“材料”）。接下來，他打算通過對作文風(fēng)格的對比，來分析他收到的這封神秘情書是否出自這些人之手。不過首先，他要找一找兩者（情書和材料）之間完全相同的句子，為了得到更可靠的分析結(jié)果，他要找到兩者之間最長的那個(gè)公共句子。不過這可不是件易事，所以他找到正在參加ACM訓(xùn)練的你，希望你能寫個(gè)程序，幫他找到這個(gè)最長公共句子。

這里你只需要完成核心工作，求出最長公共句子的長度就可以了。

?

【Input】

?

第1行只包含一個(gè)整數(shù)T（0＜T≤10），表示一共有T組測試數(shù)據(jù)。

從第2行到第3T+1行每三行為一組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行包含兩個(gè)整數(shù) m，n（0＜m、n≤100），第二行為一個(gè)長度為m的字符串，為情書的內(nèi)容。第三行為一個(gè)長度為n的字符串，為材料的內(nèi)容。為簡化處理，兩個(gè)字符串都僅包含小寫英文字母。

?

【Output】

共T行，每行對應(yīng)一組測試數(shù)據(jù)的答案（將第I組測試數(shù)據(jù)的答案輸出在第I行）。

每組測試數(shù)據(jù)的答案為一個(gè)整數(shù)：最長公共句子的長度（字符數(shù)）。

?

【Sample Input】

3

10 24

helloworld

thisisalowercasesentense

6 8

abcdef

ghijklmn

9 22

abcababab

bababcababcababababcab

【Sample Output】

?

3

0

9

?

?

【樣例說明】

?

第一組數(shù)據(jù)的最長公共句子長度為3，這是因?yàn)樵?span lang="en-us">helloworld和thisisalowercasesentense這兩個(gè)字符串中，都有一個(gè)公共的子串low,其長度為3，并且不存在長度超過3的公共字串。

第二組數(shù)據(jù)abcdef和ghijklmn完全不存在相同的子串，故其最長公共句子長度為0。

第三組數(shù)據(jù)abcababab和bababcababcababababcab都包含abcababab這個(gè)子串，其長度為9，且不存在更長的公共子串。故答案為9。

-----------------------------------------------------------------------

參考答案：

#include <stdio.h>
#include <string.h>

int T, prob;
int m, n;
char s1[110], s2[110];
int c[110][110];
int f[110][110];


int lcs(int i, int j)
{
??? if (c[i][j] != prob) {
??? ??? c[i][j] = prob;
??? ??? if (i == m || j == n || s1[i] != s2[j])
??? ??? ??? f[i][j] = 0;
??? ??? else
??? ??? ??? f[i][j] = 1+lcs(i+1,j+1);
??? }

??? return f[i][j];
}


int main()
{
??? int i, j, k, max;

??? scanf("%d", &T);
??? for (prob = 1; prob <= T; prob++) {
??? ??? scanf("%d%d", &m, &n);
??? ??? scanf("%s", s1);
??? ??? scanf("%s", s2);

??? ??? max = 0;
??? ??? for (i = 0; i < m; i++)
??? ??? ??? for (j = 0; j < n; j++) {
??? ??? ??? ??? k = lcs(i,j);
??? ??? ??? ??? if (k > max) max = k;
??? ??? ??? }

??? ??? printf("%d\n", max);
??? }

??? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的TongJI Online Judge预赛（2）: LOVE LETTER的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。