POJ 2217-Secretary（后缀数组+高度数组-最大公共子串长度）

灰太狼 2022-06-17 08:57 131阅读 0赞

Secretary

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;1382</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;568</td> 
  </tr> 
 </tbody> 
</table>

Description

The basic condition of success of a political party, it is the good Election Programme. PSOS know about it, so they entrust the top secretary Juliet with this task. Because she wanted to make her work easier, she used her charm to talk round her friend Romeo to help her. Romeo is assistent of another political party and he was writing the programme some time ago. While writing the Programme for Juliet, he used some parts of his previous programme. When he gave the finished Programme to Juliet, they recognized that both programmes are too similar and that someone could notice it. They need to determine the longest part of text which is common to both programmes.

Input

At the first line there is a positive integer N stating the number of assignments to follow. Each assignment consists of exactly two lines of text, each of them contains at most 10000 characters. The end-of-line character is not considered to be a part of the text.

Output

Print a single line of text for each assignment. The line should contain the sentence "Nejdelsi spolecny retezec ma delku X." (The longest common part of text has X characters). Replace X with the length of the longest common substring of both texts.

Sample Input

2
    Tady nejsou zadni mimozemstani.
    Lide tady take nejsou.
    Ja do lesa nepojedu.
    V sobotu pojedeme na vylet.

Sample Output

Nejdelsi spolecny retezec ma delku 7.
    Nejdelsi spolecny retezec ma delku 5.

Source

[CTU FEE Local 1998][]

**[POJ 2774][] 买一送一~\\(≧▽≦)/~啦啦啦**

## 题目意思： ##

计算两个字符串的最大公共子串长度。

## 解题思路： ##

后缀数组+高度数组模板题。

在两个串之间插入一个不会再串中出现的字符拼接成一个新串S'，计算高度数组并求出其分属于两个不同串S和T时的最大值。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    #define MAXN 200100
    int n,k;
    string s,t;
    int sa[MAXN],lcp[MAXN];
    int rank[MAXN*2],tmp[MAXN*2];
    void construct_lcp(string s,int sa[],int lcp[])
    {
        int n=s.length();
        for(int i=0; i<=n; ++i)
            rank[sa[i]]=i;
        int h=0;
        lcp[0]=0;
        for(int i=0; i<n; ++i)
        {
            int j=sa[rank[i]-1];
            if(h>0) --h;
            for(; j+h<n&&i+h<n; ++h)
                if(s[j+h]!=s[i+h]) break;
            lcp[rank[i]-1]=h;
        }
    }
    bool compare_sa(int i,int j)//倍增法，比较rank
    {
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        else
        {
            int ri=i+k<=n?rank[i+k] :-1;
            int rj=j+k<=n?rank[j+k] :-1;
            return ri<rj;
        }
    }
    
    void construct_sa(string s,int sa[])//计算s的后缀数组
    {
        for(int i=0; i<=n; ++i)//初始长度为1，rank为字符编码
        {
            sa[i]=i;
            rank[i]=i<n?s[i] :-1;
        }
        for(k=1; k<=n; k*=2)//倍增法求后缀数组
        {
            sort(sa,sa+n+1,compare_sa);
            tmp[sa[0]]=0;
            for(int i=1; i<=n; ++i)
                tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
            for(int i=0; i<=n; ++i)
                rank[i]=tmp[i];
        }
    }
    bool contain(string s,int sa[],string t)
    {
        int a=0,b=s.length();
        while(b-a>1)
        {
            int c=(a+b)/2;
            if(s.compare(sa[c],t.length(),t)<0) a=c;
            else b=c;
        }
        return s.compare(sa[b],t.length(),t)==0;
    }
    void solve()
    {
        int sl=s.length();
        s+='\0'+t;
        n=s.length();
        construct_sa(s,sa);
        construct_lcp(s,sa,lcp);
        int ans=0;
        for(int i=0; i<s.length(); ++i)
            if((sa[i]<sl)!=(sa[i+1]<sl))
                ans=max(ans,lcp[i]);
        cout<<"Nejdelsi spolecny retezec ma delku "<<ans<<"."<<endl;
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int T;
        cin>>T;
        string temp;
        getline(cin,temp);//吃掉T后面的回车
        while(T--)
        {
            getline(cin,s);//整行输入
            getline(cin,t);
            solve();
        }
        return 0;
    }

[CTU FEE Local 1998]: http://poj.org/searchproblem?field=source&key=CTU+FEE+Local+1998
[POJ 2774]: http://blog.csdn.net/mikasa3/article/details/70344586