首页 > 专题系列 > Java解POJ > POJ 2774 Long Long Message [解题报告] Java
2013
11-12

POJ 2774 Long Long Message [解题报告] Java

Long Long Message

问题描述 :

The little cat is majoring in physics in the capital of Byterland. A piece of sad news comes to him these days: his mother is getting ill. Being worried about spending so much on railway tickets (Byterland is such a big country, and he has to spend 16 shours on train to his hometown), he decided only to send SMS with his mother.

The little cat lives in an unrich family, so he frequently comes to the mobile service center, to check how much money he has spent on SMS. Yesterday, the computer of service center was broken, and printed two very long messages. The brilliant little cat soon found out:

1. All characters in messages are lowercase Latin letters, without punctuations and spaces.

2. All SMS has been appended to each other – (i+1)-th SMS comes directly after the i-th one – that is why those two messages are quite long.

3. His own SMS has been appended together, but possibly a great many redundancy characters appear leftwards and rightwards due to the broken computer.

E.g: if his SMS is “motheriloveyou”, either long message printed by that machine, would possibly be one of “hahamotheriloveyou”, “motheriloveyoureally”, “motheriloveyouornot”, “bbbmotheriloveyouaaa”, etc.

4. For these broken issues, the little cat has printed his original text twice (so there appears two very long messages). Even though the original text remains the same in two printed messages, the redundancy characters on both sides would be possibly different.

You are given those two very long messages, and you have to output the length of the longest possible original text written by the little cat.

Background:

The SMS in Byterland mobile service are charging in dollars-per-byte. That is why the little cat is worrying about how long could the longest original text be.

Why ask you to write a program? There are four resions:

1. The little cat is so busy these days with physics lessons;

2. The little cat wants to keep what he said to his mother seceret;

3. POJ is such a great Online Judge;

4. The little cat wants to earn some money from POJ, and try to persuade his mother to see the doctor :(

输入:

Two strings with lowercase letters on two of the input lines individually. Number of characters in each one will never exceed 100000.

输出:

A single line with a single integer number – what is the maximum length of the original text written by the little cat.

样例输入:

yeshowmuchiloveyoumydearmotherreallyicannotbelieveit
yeaphowmuchiloveyoumydearmother

样例输出:

27

解题代码:

//* @author:
import java.io.*;
/**
 * coded by huangjinyc
 */


/*
 *  我的height,rank,SA的值都是从0开始计算的,排名最前的为0;SA中的直接指代字符的位置,第一个字符为0,依次计算
 *  Height也是从名次0开始计算;
 */

class Suffix {
final static int BUK_SIZE=201000;
final static int STRLEN=201000;
static int  Buket[]=new int[BUK_SIZE]; //桶排序的桶子
 char[] ch;
static int SA[]=new int[STRLEN]; //记录后缀数组
static int SA1[]=new int[STRLEN]; //在基数排序的时候的暂存中间状态的SA,两次基数排序之间。
static int Rank[]=new int[STRLEN]; //记录名次数组
static int Rank1[]=new int[STRLEN]; //用来记录上一轮的rank排名,因为i+1轮的rank要根据i轮的rank来重新排名
static int Height[]=new int[STRLEN];  //height不用讲了
 public Suffix(String s ) //初始化
 {
  ch=s.toCharArray();
 }
 public int Compare(int i,int j,int factor)
 {
 if(Rank[i]!=Rank[j])
  return (Rank[j]-Rank[i]);
 else
  return (Rank[j+factor]-Rank[i+factor]);
 
 }
 public void CreateSA()
 {
 
  
  for(int i=0;i<=256;i++)  //对刚开始的时候字符串进行基数排序,得到我们的SA和Rank初始值
  {
   Buket[i]=0;
  }
  for(int i=0;i< ch.length;i++)
  {
   Buket[ch[i]]++;
  }
  for(int i=1;i<=256;i++)
  {
   Buket[i]+=Buket[i-1];
  }
  for(int i=ch.length-1;i>=0;i--)
  {
   SA[--Buket[ch[i]]]=i;
  }
   for(int i=0;i< ch.length;i++)
   {
    Rank[i]=0;
   }
  Rank[SA[0]]=0;
   for(int i=1;i< ch.length;i++)
   {
     Rank[SA[i]]=Rank[SA[i-1]];  //根据基排序的结果依次排名
        if(ch[SA[i]]!=ch[SA[i-1]])
        {
    Rank[SA[i]]++;
     } 
   }
  int factor=1;
  while(factor< ch.length)  //factor是步长,倍增算法的因子,factor*=2
  {
  
 
   //第一轮基排序,对键值2排序
   for(int i=0;i< BUK_SIZE;i++)
   {
    Buket[i]=0;
   }
   for(int i=0;i< ch.length;i++)
   {
    if(SA[i]+factor< ch.length) //如果key2没有超出去字符串则直接将key的rank进行桶排序
    {
     Buket[Rank[SA[i]+factor]]++;
    }
   else  //超出,则给桶的0号增加1,说明key2是最小的
    {
     Buket[0]++;
    } 
   }
   for(int i=1;i< ch.length;i++)
   {
    Buket[i]+=Buket[i-1];
   }
   for(int i=ch.length-1;i>=0;i--)
   {
    if(SA[i]+factor< ch.length){  //同上,将中间状态保存在SA1中
     SA1[--Buket[Rank[SA[i]+factor]]]=SA[i];
    }else{
     SA1[--Buket[0]]=SA[i];
    }
   }
   
   ///第二轮基排序
   for(int i=0;i< ch.length;i++)
   {
    Buket[i]=0;
   }
   for(int i=0;i< ch.length;i++)
   {
       Buket[Rank[SA1[i]]]++;
   }
   for(int i=1;i< ch.length;i++)
   {
    Buket[i]+=Buket[i-1];
   }
   for(int i=ch.length-1;i>=0;i--) //利用SA1得到我们的SA
   {
    SA[--Buket[Rank[SA1[i]]]]=SA1[i];
   }
  
  int j=0;//排在第一的名次设置为0,相同key1,key2则名次是一样的
   for(int i=1;i< ch.length;i++)
   {
     //根据基排序的结果依次排名,如果SA[i]和SA[i-1]所指位置开始向后移动s*factor-1都相等,
	 //则直接rank[SA[i]]=rank[SA[i-1]],否则加1
        if(Compare(SA[i],SA[i-1],factor)!=0)
        {
    j++;
     } 
        Rank1[SA[i]]=j;
   }
   for(int i=0;i< ch.length;i++)
   //Rank1推出Rank,之所以要给出Rank1,是因为我们的Compare用到了Rank,
   //如果Compare中不用rank,顺序比较字符串的话也就可以不要Rank1
   {
    Rank[i]=Rank1[i];
   }
   factor*=2;
  }
  for(int i=0;i< ch.length;i++) //根据rank推出SA
  {
   SA[Rank[i]]=i;
  }
 
 
 }

 void CalculateHeightFast()  //根据h[i]>=h[i-1]-1,即height[rank[i]]>=height[rank[i-1]]-1,几乎是线性的算法
 {
    for(int i=0;i< Height.length;i++)
    {
     Height[i]=0;
    }
    int j=0;
    for(int i=0,k=0;i< ch.length;i++)
    {
     if(Rank[i]==0)
     {
      continue;
     }
     for(j=SA[Rank[i]-1];(i+k< ch.length&&j+k< ch.length)&&ch[i+k]==ch[j+k];)//利用K直接跳,不用从头开始进行
     { 
      k++;
     }
     Height[Rank[i]]=k;
     if(k>0)  //这里减一就是为了下一轮的height[rank[i]]>=height[rank[i-1]]-1做准备,为0就不减了
      k--;
    }
 }
}
public class Main {

 public static void main(String[] args)throws Exception{
  // TODO Auto-generated method stub
  BufferedReader in = 
   new BufferedReader(
   new InputStreamReader(System.in));
    String s1=in.readLine();
    String s2=in.readLine();
     String s=s1+"$"+s2; 
 //如字符串 abba  和 bab 应该只输出2的,如果不加”$"则输出3,所以在s1和s2中间添加一个最小的不出现的字符,如'$'
        int len1=s1.length();
        int len2=s.length();
        Suffix t=new Suffix(s);
   t.CreateSA();
   t.CalculateHeightFast();
   int b=0;
   for(int i=1;i< len2;i++)
   {
        if((t.SA[i]< len1&&t.SA[i-1]>=len1)||(t.SA[i]>=len1&&t.SA[i-1]< len1))
        {
     if(t.Height[i]>b)
       b=t.Height[i];
        }
 
   }
  
   System.out.println(b);
  
 }

}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1