大致题意:
给出多个字符串,输出每个字符串的最短非公共前缀。
大致思路:
tire的简单变形,每个节点加一个值来记录经过这个节点的字符串数即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=500;
const int mMax=100005;
class nodea{
public:
int id;
int vis; //前缀记录标志
nodea *p[26];
nodea(){
vis=0;
int i;
id=-1;
for(i=0;i<26;i++)p[i]=NULL;
}
};
nodea *root;
int cnt;
int insert(char *s){
int i;
nodea *r=root;
int l=strlen(s);
for(i=0;i<l;i++){
r->vis+=1;
if(r->p[s[i]-'a']==NULL){
r->p[s[i]-'a']=new nodea();
}
r=r->p[s[i]-'a'];
}
if(r->id==-1){
r->id=cnt;
r->vis+=1;
cnt++;
}
return r->id;
}
void getnum(char *s){
int i;
nodea *r=root;
int l=strlen(s);
for(i=0;i<l;i++){
r=r->p[s[i]-'a'];
if(r->vis==1){
for(int j=0;j<=i;j++){
cout<<s[j];
}
cout<<endl;
return;
}
}
cout<<s<<endl;
}
char str[mMax][nMax];
int main(){
int n,i,t=0;
while(scanf("%s",str[0])!=EOF){
t=1; //字符串总数
cnt=1;
root=new nodea();
insert(str[0]);
while(scanf("%s",str[t])!=EOF){
if(str[t][0]=='?')break; //这句是在调试时加上的,无实际用处~~
insert(str[t]);
t++;
}
for(i=0;i<t;i++){
cout<<str[i]<<" ";
getnum(str[i]);
}
}
return 0;
}
分享到:
相关推荐
关于tire树一些简单的使用和应用
Tire 字典树 方面的论文
NULL 博文链接:https://ansjsun.iteye.com/blog/441658
(2) 树有s个外部结点 (3) 树的高度等于X中最长串的长度 (4) 树中的结点数为O(n) (1) 在root结点中查找第('b'-'a'=1)号孩子指针,
后缀tire树(tire图),用于多字符串匹配。
NULL 博文链接:https://tanghongjun1985.iteye.com/blog/548759
数据结构指的是“一组数据的存储...数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tire树 算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
gem 'tire-am_serializers' 用法 与相同: render json : User . search ( ... ) 只有一件事,Rails默认情况下会寻找TireUserSeralizer 。 如果类不存在,它将尝试找到UserSerailizer 。 如果此模型不存在...
全面的轮胎模型。Using the Fiala Handling Force ...The Fiala tire model is the standard tire model that comes with all Adams/Tire modules. This chapter contains information for using the Fiala tire model:
MF_Tire_GUI 有助于可视化每个魔术公式参数对轮胎纵向力与滑移率曲线的重要性。 GUI 能够可视化以下版本的 Magic Formula 轮胎模型: * Pacejka 92 (MF 5.2) *佩斯卡1996 此外,MF_Tire_GUI 现在可用于拟合轮胎模型...
paper about tire model construction
Samsung Tire题目
tire forces, obtained from a multi-sensing hub (MSHub) unit, are used to estimate lateral vehicle velocity and a roll angle. In order to estimate lateral vehicle velocity, the recursive least square ...
设置 在python虚拟环境中,运行: pip install -r requirements.txt python manage.py migrate cars python manage.py createsuperuser (创建用于登录的用户) 运行应用程序 python manage.py runserver ...
DoubleArrayTrie 双端trie树的python实现 ...其与双数组Tire可以说在功能上互补; 在存储值很多且多有冲突、字符编码范围较大的情况下,双数组Trie树很可能在序列化到硬盘以及加载到内存的占用空间都远大于字典Trie树
Tire . suggest ( 'cars' , field : 'name.suggest' , term : 'au' ) . suggestions #=> ["audi", "audi 100", "audi 200", "audi 80", "audi 90", "audi a2", "audi a3", "audi a4", "audi a5", "audi a6"] 按多个...
3-tire sample code 3-tire sample code
魔术公司轮胎参数解析,用于查看轮胎在各工况下测试曲线。
胎压检测 Remote Sensing of Car Tire Pressure