2024-10-26：最长公共后缀查询。用go语言，给定两个字符串数组 wordsContainer 和 wordsQuery，要对每个 wordsQuery[i] 找到一个与其有最长公共后缀的字符串。如果有多个字符串与 wordsQuery[i] 有相同的最长公共后缀，则返回在 wordsContainer 中最早出现的那个。最后，返回一个整数数组 ans，其中 ans[i] 表示与 wordsQuery[i] 有最长公共后缀的字符串在 wordsContainer 中的下标。
输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]。
输出：[1,1,1]。
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
答案2024-10-26：
chatgpt
题目来自leetcode3093。
大体步骤如下：
1.初始化数据结构：
2.处理每一个查询字符串：
3.与每一个容器字符串比较：
4.处理没有匹配的情况：
5.填充结果数组：
6.完成遍历：
7.返回结果：
复杂度分析
1.时间复杂度：
2.空间复杂度：
总结
这个分析为你构建解决方案提供了清晰的逻辑框架，并明确了复杂度考量。
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func stringIndices(wordsContainer, wordsQuery []string) []int {
type node struct {
son [26]*node
minL, i int
}
root := &node{minL: math.MaxInt}
for idx, s := range wordsContainer {
l := len(s)
cur := root
if l < cur.minL {
cur.minL, cur.i = l, idx
}
for i := len(s) - 1; i >= 0; i-- {
b := s[i] - 'a'
if cur.son[b] == nil {
cur.son[b] = &node{minL: math.MaxInt}
}
cur = cur.son[b]
if l < cur.minL {
cur.minL, cur.i = l, idx
}
}
}
ans := make([]int, len(wordsQuery))
for idx, s := range wordsQuery {
cur := root
for i := len(s) - 1; i >= 0 && cur.son[s[i]-'a'] != nil; i-- {
cur = cur.son[s[i]-'a']
}
ans[idx] = cur.i
}
return ans
}
func main() {
wordsContainer := []string{"abcd", "bcd", "xbcd"}
wordsQuery := []string{"cd", "bcd", "xyz"}
fmt.Println(stringIndices(wordsContainer, wordsQuery))
}
在这里插入图片描述
Rust完整代码如下：
use std::cmp::Ordering;
struct Node {
son: [Option<Box<Node>>; 26],
min_l: usize,
index: usize,
}
impl Node {
fn new() -> Self {
Node {
son: Default::default(),
min_l: usize::MAX,
index: usize::MAX,
}
}
}
fn string_indices(words_container: Vec<&str>, words_query: Vec<&str>) -> Vec<usize> {
let mut root = Node::new();
for (idx, s) in words_container.iter().enumerate() {
let l = s.len();
let mut cur = &mut root;
if l < cur.min_l {
cur.min_l = l;
cur.index = idx;
}
for ch in s.chars().rev() {
let b = (ch as usize) - ('a' as usize);
if cur.son[b].is_none() {
cur.son[b] = Some(Box::new(Node::new()));
}
cur = cur.son[b].as_mut().unwrap();
if l < cur.min_l {
cur.min_l = l;
cur.index = idx;
}
}
}
let mut ans = vec![0; words_query.len()];
for (idx, s) in words_query.iter().enumerate() {
let mut cur = &mut root;
for ch in s.chars().rev() {
let b = (ch as usize) - ('a' as usize);
if cur.son[b].is_none() {
break;
}
cur = cur.son[b].as_mut().unwrap();
}
ans[idx] = cur.index;
}
ans
}
fn main() {
let words_container = vec!["abcd", "bcd", "xbcd"];
let words_query = vec!["cd", "bcd", "xyz"];
let result = string_indices(words_container, words_query);
println!("{:?}", result);
}
在这里插入图片描述
到此这篇ifstream读取中文字符串（ifstream 读取文件）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/rfx/37345.html