首页 > 代码库 > POJ 2217 Secretary
POJ 2217 Secretary
Secretary
Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 221764-bit integer IO format: %lld Java class name: Main
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
2Tady 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
解题：后缀数组。将两个串S，T链接起来。然后求lcp.sa[i]和sa[i+1]不同时在S或者不同时在T中，求满足这样条件的最大lcp。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 300000;18 int n,k,_rank[maxn],sa[maxn],lcp[maxn],tmp[maxn];19 char ss[100010];20 bool cmp_sa(int i,int j){21 if(_rank[i] != _rank[j]) return _rank[i] < _rank[j];22 int ri = i+k <= n ? _rank[i+k]:-1;23 int rj = j+k <= n ? _rank[j+k]:-1;24 return ri < rj;25 }26 void construct_sa(char *S,int *sa){27 for(int i = 0; i <= n; i++){28 sa[i] = i;29 _rank[i] = i < n ? S[i]:-1;30 }31 for(k = 1; k <= n; k <<= 1){32 sort(sa,sa+n+1,cmp_sa);33 tmp[sa[0]] = 0;34 for(int i = 1; i <= n; i++)35 tmp[sa[i]] = tmp[sa[i-1]] + cmp_sa(sa[i-1],sa[i]);36 for(int i = 0; i <= n; i++)37 _rank[i] = tmp[i];38 }39 }40 void construct_lcp(char *S,int *lcp){41 for(int i = 0; i <= n; i++) _rank[sa[i]] = i;42 int h = lcp[0] = 0;43 for(int i = 0; i < n; i++){44 if(h) h--;45 for(int j = sa[_rank[i]-1]; i+h < n && j+h < n && S[i+h] == S[j+h]; ++h);46 lcp[_rank[i]-1] = h;47 }48 }49 int main() {50 int t,slen;51 scanf("%d",&t);52 getchar();53 while(t--){54 gets(ss);55 slen = strlen(ss);56 ss[slen] = ‘#‘;57 gets(ss+slen+1);58 n = strlen(ss);59 memset(sa,0,sizeof(sa));60 memset(lcp,0,sizeof(lcp));61 construct_sa(ss,sa);62 construct_lcp(ss,lcp);63 int ans = 0;64 for(int i = 0; i < n; i++)65 if((sa[i] < slen) != (sa[i+1] < slen)) ans = max(ans,lcp[i]);66 printf("Nejdelsi spolecny retezec ma delku %d.\n",ans);67 }68 return 0;69 }
POJ 2217 Secretary
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。