问题背景
有一种简单的网页判重的方法，通过求两个网页内容的最长公共子序列(LCS)长度来判定两个网页的相似程度。如：
（网页A）老师：请用“果然”造句。
（网页B）学生：先吃水果，然后喝汽水……
它们的最长公共子序列为“果然”，长度为2。注意这里的“子序列”并不要求连续。
类似的，下面两个网页：
（网页A）老师：请用“果然”造句。
（网页B）学生：先吃水果，然后喝汽水，果然拉肚子……
最长公共子序列还是“果然”，长度为2。但不难看出，由于“果然”两个字在网页B中也曾连续出现，第二组网页比第一组更加“相似”。为了区分开这两种情况的区分度，我们改用一种称为LZW的理论。为了严格的叙述相似度的计算方法，我们首先定义“文本单元”。
假定网页用一个不包含空白字符（空格、回车换行、水平制表符）的字符串来表示。它只包含纯文本，没有标签。在计算相似度之前，你应该首先对该字符串进行处理，划分成一个个“文本单元”。每个文本单位可以是一个中文字、英文单词（由一个或多个连续的半角英文字母和数字组成，正规表达式为[a-zA-Z0- 9]+）、或者一个标点符号。
根据上述定义，同一个标点符号的全角和半角应该被作为不同的文本单元，尽管他们看起来可能很相近；每个单独全角英文和全角数字都应该被看成一个单独的文本单元，而连续的半角英文字母和数字应被看成一个整体。总之，全角的字符可以与中文字同等对待。
这样，网页被看成文本单元序列。例如，网页“内容？１２345６??web2.00#”切分出的文本单元序列为（为了显示方便，用下划线分隔各文本单元）：
内_容_？_１_２_345_６_?_?_web2_._00_#
而网页“why内容相似??1234567890,web#00”的切分结果为：
why_内_容_相_似_?_?_1234567890_,_web_#_00
黑体部分给出了两个网页的一个公共子序列。注意“内容”、“??”分别在两个网页中都是连续出现的文本单元。为了奖励这种情况，LZW规定一段由连续k个文本单元组成的字符串权值为k^2。在刚才的例子中，“内容”、“??”的权值均为4。但“00”是一个数字串，应当被看成一个单独的文本单元。所以权值仅为1。
根据上述规则，公共子序列“内容 ?? 00”的权值为2^2+2^2+1=9。在所有可能的子序列中，这个权值是最大的。
给定两个网页，求他们的LZW相似度，即所有可能的公共子序列中的最大权值。
注意
1) 输入的网页内容以GBK编码(参见FAQ)
2) 除了大小写英文字母和数字之外的其他半角字符均视为标点符号。
输入格式
包含两行，分别是网页A和B对应的字符串（不包含空白字符）。每行至少包含5个字节，最多包含200个字节。
输出格式
输出仅一行，包含一个整数，为两个网页的LZW相似度。
样例输入
内容？１２345６??web2.00#
why内容相似??1234567890,web#00
样例输出
9
解答：
该题主要分两部分，一部分就是解析成文本单元，另一部分就是LZW的实现，LZW其实是最长公共子序列算法的一个变形。
//============================================================================
// 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;
}