POJ2774 很长的信息

Description

Little cat在Byterland的首都读物理专业。这些天他收到了一条悲伤地信息：他的母亲生病了。担心买火车票花钱太多（Byterland是一个巨大的国家，因此他坐火车回家需要16小时），他决定只给母亲发短信。
Little cat的家境并不富裕，因此他经常去营业厅查看自己发短信花了多少钱。昨天营业厅的电脑坏掉了，打印出两条很长的信息。机智的little cat很快发现：
1.信息中所有的字符都是小写英文字母，没有标点和空格。
2.所有的短信都被连在了一起——第i+1条短信直接接在第i条短信后面——这就是这两条信息如此长的原因。
3.虽然他发的短信都被连在了一起，但由于电脑坏掉了，它们的左边或右边都可能会有许多冗余字符。
例如：如果短信是"motheriloveyou"，电脑打印出的每条信息都可能是 "hahamotheriloveyou", "motheriloveyoureally", "motheriloveyouornot", "bbbmotheriloveyouaaa"，等等。
4.因为这些乱七八糟的问题，little cat打印了两遍（所以有两条非常长的信息）。尽管原始的短信文本在两条信息中都一样，但两条信息在文本两侧的冗余字符都可能不一样。
给出这两条很长的信息，输出little cat写下的原始短信文本的最长可能长度。
背景：
在Byterland，短信按照美元/字节的单位计价。这就是little cat想要知道原始文本最长可能长度的原因。
为什么让你写一个程序？有四个原因：
1.little cat这些天忙于他的物理课程。
2.little cat不想透露他对母亲说了什么。
3.POJ是个好网站。
4.little cat想要从POJ那里挣点钱，并尝试说服他的母亲去医院

Input

两行两个由小写英文字母组成的字符串。字符串长度都不会超过100000

Output

一行一个整数，即little cat写下的原始文本的最长可能长度。

Sample Input

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother

Sample Output

题解：

将两串合并，中间插入一个'#'保证high不会交叉

直接求出hight数组然后找出满足sa分别在两串的最大hight值

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const int N=;

 char S1[N],S2[N];int s[N],n,c[N],sa[N],y[N],x[N],rk[N];

 bool comp(int i,int j,int k){

     return y[i]==y[j] && y[i+k]==y[j+k];

 }

 void getSA(){

     int m=,t=;

     for(int i=;i<=m;i++)c[i]=;

     for(int i=;i<=n;i++)c[x[i]=s[i]]++;

     for(int i=;i<=m;i++)c[i]+=c[i-];

     for(int i=n;i>=;i--)sa[c[x[i]]--]=i;

     for(int k=;k<=n;k<<=){

         t=;

         for(int i=;i<=m;i++)y[i]=;

         for(int i=n-k+;i<=n;i++)y[++t]=i;

         for(int i=;i<=n;i++)if(sa[i]>k)y[++t]=sa[i]-k;

         for(int i=;i<=m;i++)c[i]=;

         for(int i=;i<=n;i++)c[x[i]]++;

         for(int i=;i<=m;i++)c[i]+=c[i-];

         for(int i=n;i>=;i--)sa[c[x[y[i]]]--]=y[i];

         swap(x,y);

         t=x[sa[]]=;

         for(int i=;i<=n;i++)x[sa[i]]=comp(sa[i-],sa[i],k)?t:++t;

         if(t==n)break;

         m=t;

     }

     for(int i=;i<=n;i++)rk[sa[i]]=i;

 }

 int high[N];

 void gethight(){

     int h=,j;

     for(int i=;i<=n;i++){

         j=sa[rk[i]-];

         if(h>)h--;

         for(;j+h<=n && i+h<=n;h++)

             if(s[i+h]!=s[j+h])break;

         high[rk[i]-]=h;

     }

 }

 void work()

 {

     n=;

     scanf("%s%s",S1,S2);

      for(int i=,sz=strlen(S1);i<sz;i++)s[++n]=S1[i]-'a'+;

     s[++n]=;

     for(int i=,sz=strlen(S2);i<sz;i++)s[++n]=S2[i]-'a'+;

     getSA();

     gethight();

     int ans=;int tx=strlen(S1);

     for(int i=;i<n;i++)if(high[i]>ans && ((sa[i]<=tx)!=(sa[i+]<=tx)))ans=high[i];

     printf("%d\n",ans);

 }

 int main()

 {

     work();

     return ;

 }

秒客网