問題背景
有一種簡(jiǎn)單的網(wǎng)頁判重的方法，通過求兩個(gè)網(wǎng)頁內(nèi)容的最長(zhǎng)公共子序列(LCS)長(zhǎng)度來判定兩個(gè)網(wǎng)頁的相似程度。如：
（網(wǎng)頁A）老師：請(qǐng)用“果然”造句。
（網(wǎng)頁B）學(xué)生：先吃水果，然后喝汽水……
它們的最長(zhǎng)公共子序列為“果然”，長(zhǎng)度為2。注意這里的“子序列”并不要求連續(xù)。
類似的，下面兩個(gè)網(wǎng)頁：
（網(wǎng)頁A）老師：請(qǐng)用“果然”造句。
（網(wǎng)頁B）學(xué)生：先吃水果，然后喝汽水，果然拉肚子……
最長(zhǎng)公共子序列還是“果然”，長(zhǎng)度為2。但不難看出，由于“果然”兩個(gè)字在網(wǎng)頁B中也曾連續(xù)出現(xiàn)，第二組網(wǎng)頁比第一組更加“相似”。為了區(qū)分開這兩種情況的區(qū)分度，我們改用一種稱為L(zhǎng)ZW的理論。為了嚴(yán)格的敘述相似度的計(jì)算方法，我們首先定義“文本單元”。
假定網(wǎng)頁用一個(gè)不包含空白字符（空格、回車換行、水平制表符）的字符串來表示。它只包含純文本，沒有標(biāo)簽。在計(jì)算相似度之前，你應(yīng)該首先對(duì)該字符串進(jìn)行處理，劃分成一個(gè)個(gè)“文本單元”。每個(gè)文本單位可以是一個(gè)中文字、英文單詞（由一個(gè)或多個(gè)連續(xù)的半角英文字母和數(shù)字組成，正規(guī)表達(dá)式為[a-zA-Z0- 9]+）、或者一個(gè)標(biāo)點(diǎn)符號(hào)。
根據(jù)上述定義，同一個(gè)標(biāo)點(diǎn)符號(hào)的全角和半角應(yīng)該被作為不同的文本單元，盡管他們看起來可能很相近；每個(gè)單獨(dú)全角英文和全角數(shù)字都應(yīng)該被看成一個(gè)單獨(dú)的文本單元，而連續(xù)的半角英文字母和數(shù)字應(yīng)被看成一個(gè)整體。總之，全角的字符可以與中文字同等對(duì)待。
這樣，網(wǎng)頁被看成文本單元序列。例如，網(wǎng)頁“內(nèi)容？１２345６??web2.00#”切分出的文本單元序列為（為了顯示方便，用下劃線分隔各文本單元）：
內(nèi)_容_？_１_２_345_６_?_?_web2_._00_#
而網(wǎng)頁“why內(nèi)容相似??1234567890,web#00”的切分結(jié)果為：
why_內(nèi)_容_相_似_?_?_1234567890_,_web_#_00
黑體部分給出了兩個(gè)網(wǎng)頁的一個(gè)公共子序列。注意“內(nèi)容”、“??”分別在兩個(gè)網(wǎng)頁中都是連續(xù)出現(xiàn)的文本單元。為了獎(jiǎng)勵(lì)這種情況，LZW規(guī)定一段由連續(xù)k個(gè)文本單元組成的字符串權(quán)值為k^2。在剛才的例子中，“內(nèi)容”、“??”的權(quán)值均為4。但“00”是一個(gè)數(shù)字串，應(yīng)當(dāng)被看成一個(gè)單獨(dú)的文本單元。所以權(quán)值僅為1。
根據(jù)上述規(guī)則，公共子序列“內(nèi)容 ?? 00”的權(quán)值為2^2+2^2+1=9。在所有可能的子序列中，這個(gè)權(quán)值是最大的。
給定兩個(gè)網(wǎng)頁，求他們的LZW相似度，即所有可能的公共子序列中的最大權(quán)值。
注意
1) 輸入的網(wǎng)頁內(nèi)容以GBK編碼(參見FAQ)
2) 除了大小寫英文字母和數(shù)字之外的其他半角字符均視為標(biāo)點(diǎn)符號(hào)。
輸入格式
包含兩行，分別是網(wǎng)頁A和B對(duì)應(yīng)的字符串（不包含空白字符）。每行至少包含5個(gè)字節(jié)，最多包含200個(gè)字節(jié)。
輸出格式
輸出僅一行，包含一個(gè)整數(shù)，為兩個(gè)網(wǎng)頁的LZW相似度。
樣例輸入
內(nèi)容？１２345６??web2.00#
why內(nèi)容相似??1234567890,web#00
樣例輸出
9
解答：
該題主要分兩部分，一部分就是解析成文本單元，另一部分就是LZW的實(shí)現(xiàn)，LZW其實(shí)是最長(zhǎng)公共子序列算法的一個(gè)變形。
//============================================================================
// Name : LZW.cpp
// Author : Yovn
// Version :
// Copyright : yovnchine@gmail.com
//============================================================================
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
void parseToLZWLine(const char* in, int inLen, char**& out, int& actualLen) {
int mark=0;
actualLen=0;
out=new char*[inLen];
for (int i=0; i<inLen; i++) {
char ch=in[i];
if (ch<0) {
if (mark<i) {
out[actualLen]=new char[i-mark+1];
strncpy(out[actualLen], in+mark, i-mark);
out[actualLen][i-mark]='\0';
actualLen++;
}
out[actualLen]=new char[3];
out[actualLen][0]=ch;
out[actualLen][1]=in[++i];
out[actualLen][2]='\0';
actualLen++;
mark=i+1;
} else if ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9')) {
continue;
} else//only one case left
{
if (mark<i) {
out[actualLen]=new char[i-mark+1];
strncpy(out[actualLen], in+mark, i-mark);
out[actualLen][i-mark]='\0';
actualLen++;
}
out[actualLen]=new char[2];
out[actualLen][0]=ch;
out[actualLen][1]='\0';
actualLen++;
mark=i+1;
}
}
if (mark<inLen) {
out[actualLen]=new char[inLen-mark+1];
strncpy(out[actualLen], in+mark, inLen-mark);
out[actualLen][inLen-mark]='\0';
actualLen++;
}
}
void printLZWStr(char** lzwStr, int lzwLen) {
for (int i=0; i<lzwLen; i++) {
printf("%s", lzwStr[i]);
if (i<lzwLen-1) {
printf("_");
}
}
printf("\n");
}
void freeLZWStr(char** lzwStr, int lzwLen) {
for (int i=0; i<lzwLen; i++) {
delete[] lzwStr[i];
}
delete[] lzwStr;
}
int calcLZW(char** left, int leftLen, char** right, int rightLen) {
//printLZWStr(left, leftLen);
//printLZWStr(right, rightLen);
int** result=new int*[leftLen+1];
int** len=new int*[leftLen+1];
for (int i=0; i<=leftLen; i++) {
result[i]=new int[rightLen+1];
len[i]=new int[rightLen+1];
result[i][0]=0;
len[i][0]=0;
}
memset(result[0], 0, sizeof(int)*(rightLen+1));
memset(len[0], 0, sizeof(int)*(rightLen+1));
for (int i=1; i<=leftLen; i++) {
for (int j=1; j<=rightLen; j++) {
if (strcmp(left[i-1], right[j-1])==0) {
//back trace one
len[i][j]=len[i-1][j-1]+1;
result[i][j]=result[i-1][j-1]-(len[i-1][j-1]*len[i-1][j-1])
+(len[i][j]*len[i][j]);
} else if (result[i-1][j]>=result[i][j-1]) {
result[i][j]=result[i-1][j];
} else {
result[i][j]=result[i][j-1];
}
}
}
int ret= result[leftLen][rightLen];
for (int i=0; i<=leftLen; i++) {
delete[] result[i];
delete[] len[i];
}
delete[] result;
delete[] len;
return ret;
}
int main() {
char** lzwStr1=NULL;
char** lzwStr2=NULL;
string str1;
string str2;
int lzwLen1=0;
int lzwLen2=0;
getline(cin,str1);
getline(cin,str2);
parseToLZWLine(str1.c_str(), strlen(str1.c_str()), lzwStr1, lzwLen1);
parseToLZWLine(str2.c_str(), strlen(str2.c_str()), lzwStr2, lzwLen2);
cout<<calcLZW(lzwStr1, lzwLen1, lzwStr2, lzwLen2)<<endl;
freeLZWStr(lzwStr1, lzwLen1);
freeLZWStr(lzwStr2, lzwLen2);
return 0;
}