当前位置: 首页 > news >正文

如何简单制作自己的网站/企业策划书

如何简单制作自己的网站,企业策划书,wordpress分城市访问,即时设计生成网页题目链接:uva 12338 - Anti-Rhyme Pairs 题目大意:给定若干个字符串,每次询问两个字符串的最长公共前缀。 解题思路:本来应该将每个字符串连接起来做后缀数组,但其实可以直接把一个字符串看成是一个字符,然…

题目链接: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;
}

http://www.jmfq.cn/news/4750237.html

相关文章:

  • 在线手机网站预览/全网品牌推广
  • 做网站的个人心得/电商详情页模板免费下载
  • 专门做网站的公司 南阳/苏州关键词seo排名
  • 如何做网站推广最有效/网站优化方案模板
  • 社交网站开发实例/百度指数是啥
  • 网站设计书的结构/sem培训学校
  • 搜关键词可以搜到的网站怎么做/电商培训内容有哪些
  • 新手网站怎么做站长联盟网上赚钱/成人再就业培训班
  • 肇庆网站制作/网址之家大全
  • 个人网站免费制作/黄冈seo
  • 建站哪家好 discuz/2024年瘟疫大爆发
  • 网站代码开发定制/烘焙甜点培训学校
  • 推荐小蚁人网站建设/网页制作费用大概多少
  • 华为网站开发/百度客服电话24小时人工服务热线
  • 怎么样做国际网站生意/百度竞价推广后台
  • 顶尖的设计网站/外包公司是正规公司吗
  • 防止网站被攻击/网络推广产品要给多少钱
  • 如何才能做好品牌网站建设/网络营销的方式
  • wordpress获得最新评论/上海网站排名优化公司
  • wordpress单屏模板/seo快速排名优化方式
  • b2c电子商务网站的特点及类型/企业qq和个人qq有什么区别
  • 网页游戏名字排行榜/seo顾问阿亮
  • wordpress b2c建站/推广策划方案
  • 品牌免费网站建设/微信公众号小程序怎么做
  • 做像58同城这样的网站能用mysql数据库吗/杭州网站seo推广
  • 大淘客平台怎么做分销网站/代运营公司排行榜
  • javaweb界面设计/win7优化大师
  • 佛山市桂城建设局网站/什么关键词可以搜到那种
  • 做兼职网站的主要参考文献/站长之家字体
  • 新开传奇网站发布网单/软件开发一般需要多少钱