a168. 3901 - Editor＠Morris' Blog｜PChome Online 個人新聞台

2011-06-28 16:11:04| 人氣1,178| 回應1 | 上一篇 | 下一篇

a168. 3901 - Editor

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

Mr. Kim is a professional programmer. Recently he wants to design a new editor which has as many functions as possible. Most editors support a simple search function that finds one occurrence (or all occurrences successively) of a query pattern string in the text.

Mr. Kim 是一家專業的程序員。最近他要設計一個新的編輯器，有許多功能越好。大多數編輯支持一個簡單的搜索功能，找到了一個出現（或所有出現先後）查詢的模式字符串中的文本。

He observed that the search function in commercial editors does nothing if no query pattern is given. His idea of a new search function regards each substring of the given text as a query pattern string itself and his new function finds another occurrence in the text. The problem is that there can be occurrences of many substrings in the text. So, Mr. Kim decides that the new function finds only occurrences of the longest substring in the text in order to remedy the problem. A formal definition of the search function is as follows:

他發現在商業搜索功能編輯器不執行任何操作，如果沒有查詢模式給出。他的想法的一個新的搜索功能對於每個子串給定的文本查詢模式字符串本身和他的新功能的發現另一個出現在文本中。問題是，可以有許多子字串出現在文本中。所以，Mr. Kim 決定，新功能只查找子串出現的最長的文本，以解決這個問題。正式定義的搜索功能如下：

Given a text string S , find the longest substring in text string S such that the substring appears at least twice. The two occurrences are allowed to overlap.

給定一個文本字符串S，找到最長的子串串S中文字，這樣的子串出現至少兩次。這兩個事件都可以重疊。

輸入說明：

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. For each test case, a text string S is given in one line. For every string, the length is less than or equal to 5,000 and the alphabet

is the set of lowercase English characters.

輸出說明：

Your program is to write to standard output. Print exactly one line for each test case. Print the length of the longest substring in text string S such that the substring appears at least twice.

範例輸入：

3 
abcdefghikjlmn
abcabcabc
abcdabcabb

範例輸出：

0 
6 
3

提示：

// abcabcabc

最長 abcabc，因為abcabcabc、abcabcabc

// abcdabcabb

最長 abc，因為abcdabcabb、abcdabcabb

出處：

ACM 3901 (管理：morris1028)

作法 : Suffix array (SA)
建lcp
求高度數組的最大值

/**********************************************************************************/
/* Problem: a168 "3901 - Editor" from ACM 3901                                   */
/* Language: C                                                                   */
/* Result: AC (340ms, 432KB) on ZeroJudge                                        */
/* Author: morris1028 at 2011-06-23 22:48:20                                     */
/**********************************************************************************/

#include<stdio.h>
#include<string.h>
#define MaxL 5002
void Merge(int, int, int);
void MergeSort(int, int);

struct xy_change_rank{
   int index, v;
}Data[MaxL], X[MaxL];
char S[MaxL], base_rank[256];
int s2[20]={1}, rank[MaxL], SA[MaxL], L;
int height_Build(int);
void MergeSort(int, int);
void Merge(int, int, int);

void Doubling_Algorithm() {
    int a, b, C, temp;
    L=strlen(S);
    int Queue[MaxL] = {-1};
    char Mask[MaxL];

    for(a = 0; a < L; a++)
        rank[a] = base_rank[S[a]], Mask[a] = 0,
        Data[a].v = rank[a], Data[a].index = a;
    MergeSort(0, L-1);
    for(a = 0; s2[a] < L; a++) {
        temp = Data[0].v, C = 1;
        for(b = 0; b < L; b++) {
            if(Data[b].v != temp || Mask[b] == 1)
                Queue[C] = b-1, temp = Data[b].v, C++, Mask[b] = 1;
            rank[Data[b].index] = C;
        }
        Queue[C] = L-1, C++;
        for(b = 0; b < L; b++) {
            if(Data[b].index + s2[a]<L) Data[b].v = rank[Data[b].index + s2[a]];
            else Data[b].v = 0;
        }
        for(b = 1; b < C; b++)
            MergeSort(Queue[b-1]+1, Queue[b]);
    }
    for(a = 0; a < L; a++)
        SA[a] = Data[a].index;
    height_Build(L);
}
int height[MaxL];
int height_Build(int L) {
    int a, b, k = 0;
    for(a = 0; a < L; a++)    rank[SA[a]] = a;
    for(a = 0; a < L; a++) {
        if(rank[a] == 0) {height[rank[a]] = 0; continue;}
        if(a == 0 || height[rank[a-1]] <= 1) k = 0;
        else k = height[rank[a-1]] - 1;
        while(S[SA[rank[a]-1]+k] == S[SA[rank[a]]+k])    k++;
        height[rank[a]] = k;
    }
}
main() {
    int a, T;
    for(a = 1; a < 20; a++)   s2[a] = s2[a-1]*2;
    for(a = 32; a <= 126; a++)   base_rank[a] = a;
    scanf("%d", &T);
    getchar();
    while(T--) {
        gets(S);
        Doubling_Algorithm();
        int Ans = 0, L = strlen(S);
        for(a = 0; a < L; a++) {
            Ans = (Ans > height[a]) ? Ans : height[a];
        }
        printf("%d\n", Ans);
    }
    return 0;
}
void MergeSort(int l, int h) {
    if(l < h) {
        int m=(l+h)/2;
        MergeSort(l ,m);
        MergeSort(m+1,h);
        Merge(l,m,h);
    }
}
void Merge(int l, int m, int h) {
    int In1 = l, In2 = m+1;
    int a, b, Top = 0;
    while(In1 <= m && In2 <= h)
        if(Data[In1].v <= Data[In2].v)
             X[Top++] = Data[In1++];
       else X[Top++] = Data[In2++];
    while(In1 <= m)   X[Top++] = Data[In1++];
    while(In2 <= h)   X[Top++] = Data[In2++];
    for(a = 0, b = l; a < Top; a++, b++)
        Data[b] = X[a];
}

我要檢舉

#a168#3901 - Editor

台長： Morris

您可能對以下文章有興趣

[資料結構] BST 的 construct & traversal

[演算法][程式作業] Edit distance

[演算法][程式作業] huffman code 壓縮與解壓縮

[数据结构与算法] 第13周高级数据结构（1）

人氣(1,178) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 其他題目 |
此分類下一篇:a073. POJ2832 How Many Pairs?
此分類上一篇:a167. SPOJ 694. Distinct Substrings

回應(1)