挑战程序竞赛系列(71):4.7高度数组(1)

挑战程序竞赛系列(71):4.7高度数组(1)

传送门:POJ 2217: Secretary

题意:

给定两个字符串S和T。请计算两个字符串最长的公共字符串子串的长度。

LCP概念:在后缀数组中相邻两个后缀的最长公共前缀(Longest Common Prefix)

的确很取巧,相邻位置的最长公共前缀可以由前一个位置的最长公共前缀得出,至少在h-1个位置上不需要再比较,而直接比较后续的字符即可。

代码如下:

import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main{

    String INPUT = "./data/judge/201709/P2217.txt";

    static Scanner in;
    public static void main(String[] args) throws IOException {
        in = new Scanner(System.in);
        new Main().run();
    }

    void read() {
        int t = in.nextInt();
        in.nextLine();
        while (t --> 0) {
            String S = in.nextLine();
            String T = in.nextLine();
            StringBuilder sb = new StringBuilder();
            sb.append(S + '$' + T);
            SuffixArray sa = new SuffixArray(sb.toString().toCharArray());
            int max = 0;
            for (int i = 0; i < sb.length(); ++i) {
                if (sa.sa[i] < S.length() != sa.sa[i + 1] < S.length())
                    max = Math.max(max, sa.lcp[i]);
            }
            System.out.println("Nejdelsi spolecny retezec ma delku " + max + ".");
        }
    }

    class SuffixArray{
        int k = 1;
        int n;
        Integer[] sa;
        int[] rank, tmp;
        int[] lcp;

        SuffixArray(char[] cs){
            n    = cs.length;
            sa   = new Integer[n + 1];
            rank = new int[n + 1];
            tmp  = new int[n + 1];
            lcp  = new int[n];
            for (int i = 0; i <= n; ++i) {
                sa[i] = i;
                rank[i] = i < n ? cs[i] : -1;
            }

            for (k = 1; k <= n; k <<= 1) {
                Arrays.sort(sa, cmp);
                tmp[sa[0]] = 0;
                for (int i = 1; i <= n; ++i) {
                    tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.compare(sa[i - 1], sa[i]) < 0 ? 1 : 0);  
                }

                for (int i = 0; i <= n; ++i) {
                    rank[i] = tmp[i];
                }
            }

            // lcp
            for (int i = 0; i <= n; ++i) rank[sa[i]] = i;  //求出每个后缀的当前排名
            int h = 0;
            for (int i = 0; i < n; ++i) {
                int j = sa[rank[i] - 1]; // 后缀i的前一个后缀
                if (h > 0) h--;
                for (;j + h < n && i + h < n; ++h) {
                    if (cs[j + h] != cs[i + h]) break;
                }
                lcp[rank[i] -1] = h;
            }

        }



        private Comparator<Integer> cmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int i = o1;
                int j = o2;
                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 run() throws IOException {
        read();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

【编程题】Java编程题三(10道)

【编程题】Java编程题三(10道) 【程序21】 题目:求1+2!+3!+...+20!的和 public class lianxi21 { publ...

3526
来自专栏函数式编程语言及工具

Scalaz(24)- 泛函数据结构: Tree-数据游览及维护

上节我们讨论了Zipper-串形不可变集合(immutable sequential collection)游标,在串形集合中左右游走及元素维护操作。这篇我...

1896
来自专栏鸿的学习笔记

python的字典和集合

dict类型可以说是python里模块的命名空间,实例的属性,函数的关键字参数都有其的参与。

923
来自专栏一枝花算不算浪漫

[读书笔记]C#学习笔记五: C#3.0自动属性,匿名属性及扩展方法

34010
来自专栏有趣的django

第二章、深入类和对象

1960
来自专栏西安-晁州

TypeScript学习笔记之类

TypeScript的类,简单地定义如下: class Person { x: number; // 默认为public类型 y: ...

2150
来自专栏赵俊的Java专栏

记一道 Java 综合面试题

1972
来自专栏函数式编程语言及工具

Scalaz(27)- Inference & Unapply :类型的推导和匹配

 经过一段时间的摸索,用scala进行函数式编程的过程对我来说就好像是想着法儿如何将函数的款式对齐以及如何正确地匹配类型,真正是一种全新的体验,但好像有点太偏...

1958
来自专栏Java3y

给女朋友讲解什么是Optional【JDK 8特性】

前两天带女朋友去图书馆了,随手就给她来了一本《与孩子一起学编程》的书,于是今天就给女朋友讲解一下什么是Optional类。

523
来自专栏函数式编程语言及工具

Scalaz(12)- Monad:再述述flatMap,顺便了解MonadPlus

  在前面的几篇讨论里我们初步对FP有了些少了解:FP嘛,不就是F[A]吗?也是,FP就是在F[]壳子(context)内对程序的状态进行更改,也就是在F壳子(...

1857

扫码关注云+社区