题目链接:uva 12338 - Anti-Rhyme Pairs
题目大意:给定若干个字符串,每次询问两个字符串的最长公共前缀。
解题思路:本来应该将每个字符串连接起来做后缀数组,但其实可以直接把一个字符串看成是一个字符,然后排序了就对应是SA数组,然后处理height即可。然后根据后缀数组的性质,字符串i和j的最长公共前缀长度即为rank[i]+1~rank[j]之间height的最小值。特判i=j的情况。
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<string, int> pii;
const int maxn = 1e5+5;
int Rank[maxn];
int dp[maxn][20];
vector<pii> g;
vector<int> height;
void rmq_init(const vector<int>& A) {
int n = A.size();
for (int i = 0; i < n; i++)
dp[i][0] = A[i];
for (int j = 1; (1<<j) <= n; j++) {
for (int i = 0; i + (1<<j) - 1 < n; i++)
dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
int rmq_query (int l, int r) {
if (l == r)
return g[l].first.length();
if (l > r)
swap(l, r);
l++;
int k = 0;
while ((1<<(k+1)) <= r - l + 1)
k++;
return min(dp[l][k], dp[r - (1<<k) + 1][k]);
}
void solve () {
sort(g.begin(), g.end());
for (int i = 0; i < g.size(); i++)
Rank[g[i].second] = i;
height.clear();
height.push_back(0);
for (int i = 1; i < g.size(); i++) {
int n = min(g[i].first.length(), g[i-1].first.length());;
int j;
for (j = 0; j < n; j++)
if (g[i].first[j] != g[i-1].first[j])
break;
height.push_back(j);
}
rmq_init(height);
}
int main () {
int cas, n, l, r;
string s;
cin >> cas;
for (int kcas = 1; kcas <= cas; kcas++) {
cin >> n;
g.clear();
for (int i = 0; i < n; i++) {
cin >> s;
g.push_back(make_pair(s, i));
}
solve();
cout << "Case " << kcas << ":" << endl;
cin >> n;
while (n--) {
cin >> l >> r;
cout << rmq_query(Rank[l-1], Rank[r-1]) << endl;
}
}
return 0;
}
分享到:
相关推荐
keras-quora-question-pairs, 一个Keras模型,解决了Quora问题对的二 keras-quora-question-pairs一个Keras模型,它解决了Quora的问题对 [1] 。模型实现Keras模型体系结构如下所示: model architecture ...
auto-pairs是vim的一个极小的插件。它对于用vim来编写程序,提供了极大的便。我ubuntu16中,用vim编写c和c++程序,安装了此插件,极大地方便了代码的输入。 二、功能介绍: 它可以自动完成大括号、小括号、中括号、...
前端开源库-ripple-keypairs波纹键对,波纹键对
摘要:判断两个文章之间的关系,例如两个文章是否在讨论同一个事件,对于很多文本理解任务有重要意义。目前的算法较少处理长文本匹配的问题,也缺乏对长文本语义结构的充分
leetcode伪代码numbers-of-good-pairs 题目解读: 题目来源: 原文: Given an array of integers nums. A pair (i,j) is called good if nums[i] == nums[j] and i < j. Return the number of good pairs. 解读: ...
不会LeetCode_532--K-diff-Pairs-in-an-Array 给定一个整数数组和一个整数 k,您需要找到数组中唯一 k-diff 对的数量。 这里 k-diff 对定义为整数对 (i, j),其中 i 和 j 都是数组中的数字,它们的绝对差为 k。 示例...
In this paper, we introduce a method to detect co-saliency from an image pair that may have some objects in common. The co-saliency is modeled as a linear combination of the single-image saliency map ...
功能是: xah-replace-pairs-region Xah替换成对的字符串xah-replace-regexp-pairs-region xah-replace-regexp-pairs-in-string xah-replace-pairs-region-recursive xah-replace-pairs-in-string-recursive 详情见...
kaggle Quora Question Pairs
•2 - Differential pairs push-pull CPU @0.8V or @3.3V •6 - Differential pairs push-pull PCI-E @0.8V •1 - Differential pairs push-pull SATA @0.8V or PCI-E @0.8V •1 - Differential pairs push-pull DOT...
Attacks and Improvement of Quantum Sealed-Bid Auction with EPR Pairs
作业说明 代码注释中有力扣链接. 第一周作业 循环队列, 双向循环队列, 双向队列, ...两两交换链表中的节点, swap-nodes-in-pairs.ts 三数之和, three-sum.ts 接雨水, trapping-rain-water.ts 两数之和,
视觉问答数据集_含1456张场景图片+对应qa.pairs+训练测试集划分整理_可用于深度学习多模态算法训练
./persistent-hdfs/bin/hadoop fs -rm /vol/all-pairs-shortest-path_2.10-1.0.jar ./persistent-hdfs/bin/hadoop fs -put all-pairs-shortest-path_2.10- 1.0.jar hdfs://ec2-54-146-149-83.compute-1.amazonaws....
-----+--------------------+-------------+-------------+ | | | | V V | | +---------+ n0, n1 +----------+ | | | Model 1 |--------->| Mixer 1 |\ p | | +---------+ \ / | | \ V V \ / +----------+ \ ...
论文
来自https://github.com/abhishekkrthakur/is_that_a_duplicate_quora_question
Context_Free_Grammar-Noun_Adjective_Pairs 使用上下文无关的语法块规则从文本中查找名词形容词对。
We demonstrate an efficient experimental scheme for producing polarization-entangled photon pairs from spontaneous four-wave mixing (SFWM) in a laser-cooled 85Rb atomic ensemble, with a bandwidth (as ...
我使用图像的CLIP嵌入的余弦相似度创建了一个Image-Text-Pairs数据集,该图像的标题来自YFCC100M。 我还从NSFW检测器中添加了以下功能:“性感”,“色情”,“绘图”,“无尽”,“中性” 图像-文本对的数量:...