社区讨论

为什么用字典树会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 条回复,欢迎继续交流。

正在加载回复...