建设部职业资格注册中心网站,怎么自己公司名下的网站,点击排名优化,自建网站成都目录
E. Collapsing Strings
题目大意#xff1a;
思路#xff1a;
代码: E. Collapsing Strings
Problem - E - Codeforces
题目大意#xff1a;
给你n个字符串#xff0c;然后对任意两个字符串进行合并操作#xff0c;
设两个字符串 a 和 b 的折叠 C(a,b) 是以下…目录
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)ab 即两个字符串的串联。
然后计算任意两个字符串合并后的长度和。
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];}}
}
