社区讨论
为什么用字典树会MLE???
P3370【模板】字符串哈希参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo8ewmhq
- 此快照首次捕获于
- 2023/10/27 17:29 2 年前
- 此快照最后确认于
- 2023/10/27 17:29 2 年前
CPP
#include<iostream>
#include<string>
using namespace std;
typedef struct Node{
char c;
bool isEnd;
Node*nodePointer[75];
Node(char _c='\0'):c(_c),isEnd(false){
for(int i=0;i<75;i++){
nodePointer[i]=nullptr;
}
}
}Node;
Node*root=new Node;
int ans=0;
bool hasNullString=false;
void insertORfind(const string& str){
if(str==""){
hasNullString=true;
return;
}
Node*temp=root;
int len=str.length();
for(int i=0;i<len;i++){
if(temp->nodePointer[str[i]-'0']==nullptr){
temp->nodePointer[str[i]-'0']=new Node(str[i]);
}
if(i==len-1){
if(!temp->nodePointer[str[i]-'0']->isEnd){
temp->nodePointer[str[i]-'0']->isEnd=true;
ans++;
}
}
temp=temp->nodePointer[str[i]-'0'];
}
}
int main(){
int N;
cin>>N;
string str;
for(int i=0;i<N;i++){
cin>>str;
insertORfind(str);
}
cout<<(hasNullString?ans+1:ans)<<endl;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...