Visits: 97

计蒜客 新年礼物

新年了，蒜厂 BOSS 要给小蒜头们发新年礼物，新年礼物有很多份，怎么分配这些礼物呢？蒜厂 BOSS 打算让大家玩一个游戏。

蒜头们可以从抽奖箱里抽出 $N$ 个字符串，第 $i$ 个是 $x_i$，按抽出的顺序从 $1$ 编号。一个蒜头可以得到的礼物个数决定于一个特别的子序列（不要求连续）。当且仅当 $x_i$ 是 $x_j$ 的前缀，$x_i$ 也是 $x_j$ 的后缀时，字符串 $x_i$ 和 $x_j$($i \lt j$) 能在一个子序列中。一个蒜头可以得到的礼物个数符合要求的子序列中最长的那个的长度。

输入格式

第一行输入一个整数 $N$，紧接着输入 $N$ 行字符串，每个字符串仅包含小写或大写字母。

输入数据总共少于 $2\times 10^6$ 个字符。

输出格式

答案输出在一行，一个整数，表示这个蒜头能得到的礼物个数。

样例 1

5
A
B
AA
BBB
AAA

3

样例 2

5
A
ABA
BBB
ABABA
AAAAAB

3

这道题首先要用拓展 KMP 做一次预处理，记录每个字符串哪些位置的前缀和后缀相同。

private static int[] extendedKMP(String t) {
    int n = t.length();
    int[] next = new int[n];
    next[0] = n;
    int p = 0;
    while (p < n - 1 && t.charAt(p) == t.charAt(p + 1)) {
        p++;
    }
    next[1] = p;
    int k = 1, l;
    for (int i = 2; i < n; i++) {
        p = k + next[k] - 1;
        l = next[i - k];
        if (i + l - 1 < p) {
            next[i] = l;
        } else {
            int j = p - i + 1;
            if (j < 0) {
                j = 0;
            }
            while (i + j < n && t.charAt(i + j) == t.charAt(j)) {
                j++;
            }
            next[i] = j;
            k = i;
        }
    }
    return next;
}

然后我们就可以把字符串插入到前缀树中了。在插入的过程中，始终用 dp[] 数组记录下当前满足条件的最大值，最后只需要遍历 dp[] 数组，找到最大值就是答案。

public static void main(String[] args) {
    int n = in.nextInt();
    Trie t = new Trie();
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        String s = in.next();
        int[] next = extendedKMP(s);
        t.insert(s, next);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = Math.max(ans, dp[i]);
    }
    System.out.println(ans);
}

在插入的过程中，当满足 isEnd() 这个条件的时候，word 到当前位置为止的前缀是一个已经存在的子串 $x_i$，所以前缀的性质满足，只需要检查是不是后缀。

这个前缀的长度 len = i + 1，如果距离最后为 len 的那个位置上，它满足的前缀长度恰好是 len，那么就是满足的。

if (node.isEnd()) {
    // 当满足 isEnd() 这个条件的时候，word 到当前位置为止的前缀是一个已经存在的子串 xi
    // 所以前缀的性质满足，只需要检查是不是后缀
    // 这个前缀的长度 len = i + 1
    int len = i + 1;
    // 如果距离最后为 len 的那个位置上，它满足的前缀长度恰好是 len，那么就是满足的
    if (next[word.length() - len] == len) {
        // TODO
    }
}

对于满足条件的值，我们需要记录下当前满足条件的最大值。

为了编程的方便，我在前缀树的结点中增加了一个字段，用来记录当前结点对应的单词的编号，即对应 dp[] 数组的下标。

private int index;

public void setEnd(int index) {
    end = true;
    this.index = index;
}

public int getIndex() {
    return index;
}

最后，在上面的 TODO 中填上如下内容：

if (next[word.length() - len] == len) {
    dp[index] = Math.max(dp[index], dp[node.getIndex()] + 1);
}

注意 dp[] 数组应该被初始化为 1，而不是 0。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {

    static Scanner in = new Scanner(System.in);

    private static int[] extendedKMP(String t) {
        int n = t.length();
        int[] next = new int[n];
        next[0] = n;
        if (n == 1) {
            // 注意 corner case，否则会出现数组越界
            return next;
        }
        int p = 0;
        while (p < n - 1 && t.charAt(p) == t.charAt(p + 1)) {
            p++;
        }
        next[1] = p;
        int k = 1, l;
        for (int i = 2; i < n; i++) {
            p = k + next[k] - 1;
            l = next[i - k];
            if (i + l - 1 < p) {
                next[i] = l;
            } else {
                int j = p - i + 1;
                if (j < 0) {
                    j = 0;
                }
                while (i + j < n && t.charAt(i + j) == t.charAt(j)) {
                    j++;
                }
                next[i] = j;
                k = i;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        Trie t = new Trie();
        int[] dp = new int[n];
        // 赋初值为 1，因为至少自己是满足条件的
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            String s = in.next();
            int[] next = extendedKMP(s);
            t.insert(s, next, i, dp);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }

}

class Trie {

    private TrieNode root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new TrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word, int[] next, int index, int[] dp) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.contains(c)) {
                node.put(c);
            }
            node = node.get(c);
            if (node.isEnd()) {
                // 当满足 isEnd() 这个条件的时候，word 到当前位置为止的前缀是一个已经存在的子串 xi
                // 所以前缀的性质满足，只需要检查是不是后缀
                // 这个前缀的长度 len = i + 1
                int len = i + 1;
                // 如果距离最后为 len 的那个位置上，它满足的前缀长度恰好是 len，那么就是满足的
                if (next[word.length() - len] == len) {
                    dp[index] = Math.max(dp[index], dp[node.getIndex()] + 1);
                }
            }
        }
        node.setEnd(index);
    }
}

class TrieNode {
    private HashMap<Character, TrieNode> links;
    private boolean end;
    private int index;

    public TrieNode() {
        links = new HashMap<>();
        end = false;
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd(int index) {
        end = true;
        this.index = index;
    }

    public int getIndex() {
        return index;
    }

    public TrieNode get(char c) {
        return links.get(c);
    }

    public void put(char c) {
        links.put(c, new TrieNode());
    }

    public boolean contains(char c) {
        return links.containsKey(c);
    }

}