长长的消息
| 时间限制： 4000MS | 内存限制： 131072K | |
| 提交总数： 32393 | 接受： 13079 | |
| 案件时间限制： 1000MS | ||
描述
小猫在拜特兰的首府物理专业。最近有一个不幸的消息传来，他的母亲生病了。担心在火车票上花费太多（拜特兰是一个如此大的国家，他不得不在火车上花费16个小时到家乡），他决定只和母亲发短信。 小猫生活在一个非常富有的家庭，所以他经常到移动服务中心去查看他在短信上花了多少钱。昨天，服务中心的电脑坏了，打印了两条很长的信息。很快就发现了这只聪明的小猫： 1.所有消息中的字符都是小写的拉丁字母，没有标点符号和空格。 2.所有短信都被相互追加 - （i + 1）短信直接在第i个短信之后 - 这就是为什么这两个短信很长。 3.他自己的短信已经被附加在一起，但是由于破损的计算机，可能有很多冗余字符向左和向右出现。 例如：如果他的短信是“motheriloveyou”，那么由该机器打印的长信息可能是“hahamotheriloveyou”，“motheriloveyoureally”，“motheriloveyouornot”，“bbbmotheriloveyouaaa”等之一 。4.对于这些破碎的问题，猫已经两次打印他的原始文本（所以出现两个很长的消息）。即使两个打印的消息中的原始文本保持不变，两边的冗余字符也可能不同。 给你这两条很长的信息，你必须输出由小猫写的最长可能的原始文本的长度。 背景： Byterland移动服务中的短信以每字节为单位收费。这就是为什么这只小猫正在担心最长的原始文本能持续多久。 为什么要你写程序？有四个方面的问题： 1，这些小猫在物理课上很忙碌; 小猫想保留他对母亲所说的话。 POJ是一个很棒的在线评委。 来自“现代汉英综合大词典”小猫想从POJ那里挣点钱，并试图说服他的母亲去看医生：
输入
在两个输入行上分别输入两个小写字母的字符串。每个字符的数量不会超过100000。
产量
单个整数的单行 - 小猫写的原始文本的最大长度是多少？
示例输入
yeshowmuchiloveyoumydearmotherreallyicannotbelieveityeaphowmuchiloveyoumydearmother
示例输出
27
经典的双串匹配最长公共长度问题
我们在第一个串末尾末尾加一个'#'这样的东西，在把第二个串连上去，这样子#一定不会参与匹配而且我们还把两个串分隔开了
接下来就是求lcp了，我们只需找到跨越#的最大的height就可以了
#include#include #include #include #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)using namespace std;const int maxn = 200005,maxm = 100005,INF = 1000000000;inline int RD(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();} return out * flag;}char s[maxn],B[maxn];int la,lb,n,m = 256,sa[maxn],rank[maxn],height[maxn],t1[maxn],t2[maxn],c[maxn];void SA(){ int *x = t1,*y = t2; for (int i = 0; i <= m; i++) c[i] = 0; for (int i = 1; i <= n; i++) c[x[i] = s[i]]++; for (int i = 1; i <= m; i++) c[i] += c[i - 1]; for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i; for (int k = 1; k <= n; k <<= 1){ int p = 0; for (int i = n - k + 1; i <= n; i++) y[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k; for (int i = 0; i <= m; i++) c[i] = 0; for (int i = 1; i <= n; i++) c[x[y[i]]]++; for (int i = 1; i <= m; i++) c[i] += c[i - 1]; for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i]; swap(x,y); p = 1; x[sa[1]] = 1; for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p; if (p >= n) break; m = p; } for (int i = 1; i <= n; i++) rank[sa[i]] = i; int k = 0; for (int i = 1; i <= n; i++){ if (k) k--; int j = sa[rank[i] - 1]; while (s[i + k] == s[j + k]) k++; height[rank[i]] = k; }}void solve(){ int ans = 0; for (int i = 2; i <= n; i++){ if (sa[i] <= la && sa[i - 1] > la || sa[i] > la && sa[i - 1] <= la){ ans = max(ans,height[i]); } } cout< <