Educational Codeforces Round 159(div2) --- E. Collapsing Strings-- 题解

目录

E. Collapsing Strings

题目大意：

思路：

代码:

E. Collapsing Strings

Problem - E - Codeforces

题目大意：

给你n个字符串，然后对任意两个字符串进行合并操作，

设两个字符串 a 和 b 的折叠 C(a,b) 是以下操作：

• 如果 a 为空，则 C(a,b)=b;
• 如果 b 为空，则 C(a,b)=a;
• 如果 a 的最后一个字母等于 b 的第一个字母，则 C(a,b)=C(a1,|a|−1,b2,|b|) ，其中 sl,r是 s 的子字符串，从  第l 个字母到 第r 个字母;
• 否则为 C(a,b)=a+b ，即两个字符串的串联。

然后计算任意两个字符串合并后的长度和。

n <= 10^6, |s| <= 10^6 并且总的字符串长度为10^6

思路：

即如果两个字符串的前缀和后缀相同，应该将这部分相同的前缀和后缀去掉（就是消消乐），然后他们剩下的字符串长度就是答案。

如果暴力求的话复杂度是len * n * n为10^18的次方，这是不能接受的，所以需要进行预处理，将部分相同的前缀和后缀全部去掉这一件事其实可以看作是寻找前缀匹配长度，如果有匹配需要删除此部分贡献的答案。

所以可以构建一个前缀树，然后在匹配时，将每一个字符串倒序，后缀就变成了前缀，便可以利用这个已经构造后的前缀树快速得到答案。

for (int i = 1; i <= n; i++) {
            str[i] = input.next();
            build(str[i]); // 构建前缀树
            sum += str[i].length();
        }
        sum *= 2L * n; // 如果没有任意一对字符串可以匹配时的答案。
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= str[i].length(); j++) ans[j] = 0;
            query(str[i]); // 
            for (int j = str[i].length() - 1; j >= 0; j--) {
            // 将拥有相同前缀和后缀的答案进行删除
                sum -= 2L * (j + 1) * (ans[j] - ans[j + 1]); 
            }
        }
public static void build(String str){
        char[] s = str.toCharArray();
        int p = 0;
        for (int i = 0; i < s.length; i++) {
            int j = s[i] - 'a';
            if (tree[p][j] == 0) tree[p][j] = ++idx;
            p = tree[p][j];
            cnt[p]++;
        }
    }

    public static void query(String str){
        char[] s = str.toCharArray();
        int p = 0;
        for (int i = 0; i < s.length; i++) {
            int k = str.length() - i - 1; // 使用对应编号，这里相当于是对逆序的优化
            int j = s[k] - 'a';
            if (tree[p][j] == 0) return; // 如果当前位置没有匹配的前缀，退出
            p = tree[p][j]; 
            ans[i] = cnt[p]; // 拥有匹配相同前缀的字符串个数
        }
    }

代码:

import java.util.Scanner;

/**
 * @ProjectName: study3
 * @FileName: Ex41
 * @author:HWJ
 * @Data: 2023/12/4 19:48
 */
public class Ex41 {
    static int N = (int) (1e6 + 6);
    static int[] cnt = new int[N];
    static int[][] tree = new int[N][30];
    static long[] ans = new long[N];
    static String[] str = new String[N];
    static int idx = 0;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            str[i] = input.next();
            build(str[i]);
            sum += str[i].length();
        }
        sum *= 2L * n;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= str[i].length(); j++) ans[j] = 0;
            query(str[i]);
            for (int j = str[i].length() - 1; j >= 0; j--) {
                sum -= 2L * (j + 1) * (ans[j] - ans[j + 1]);
            }
        }
        System.out.println(sum);
    }
    public static void build(String str){
        char[] s = str.toCharArray();
        int p = 0;
        for (int i = 0; i < s.length; i++) {
            int j = s[i] - 'a';
            if (tree[p][j] == 0) tree[p][j] = ++idx;
            p = tree[p][j];
            cnt[p]++;
        }
    }

    public static void query(String str){
        char[] s = str.toCharArray();
        int p = 0;
        for (int i = 0; i < s.length; i++) {
            int k = str.length() - i - 1;
            int j = s[k] - 'a';
            if (tree[p][j] == 0) return;
            p = tree[p][j];
            ans[i] = cnt[p];
        }
    }
}