相似和

[编程题]相似和

热度指数：352 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出n个字符串串 $s_1,s_2,...s_n$

定义两个字符串 ${s}$ , ${t}$ 的相似度 ${f(s,t)}$ 为他们的最长公共前缀长度

求 $\sum_{i=1}^{n-1}\sum_{j=i+1}^nf(s_i,s_j)$

保证所有出现的字符均为'a'~'z'的小写英文字母

示例1

输入

3,["niuniu","niumei","niuneng"]

输出

说明

"niuniu"与"niumei"的相似度为3
"niuniu"与"niuneng"的相似度为4
"niumei"与"niuneng"的相似度为3
所以相似度的总和为10

备注:


第一个参数n表示字符串个数
第二个参数s包含n个字符串

算法知识视频讲解

摸鱼学大师

发表于 2021-08-11 19:24:01

思路：题目的主要信息：字符串的相似度定义为两个字符串的相同字符前缀长度对于n个字符串，求任意两个字符串的相似度，并求总和只出现小写字母a-z 方法一：暴力法具体做法： class Solution { public: int similarity(string& s1, 展开全文

Peterliang

发表于 2021-10-11 01:00:30

NC558 题解 | #相似和# 题意分析给出n个字符串串s1,s2,...sns_1,s_2,...s_ns1,s2,...sn 定义两个字符串s,ts,ts,t的相似度f(s,t)f(s,t)f(s,t)为他们的最长公共前缀长度求 ∑i=1n−1∑j=i+1nf(si,sj)\su 展开全文

CroMarmot

发表于 2021-10-01 03:32:03

题意 nnn 个字符串, 求两两之间的公共最长前缀的长度和范围限制n≤105n \leq 10^5n≤105, 所有字符串长度和≤106\leq 10^6≤106 算法朴素的暴力方法直接按照题意实现的话需要字符串之间两两比较。代码 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接展开全文