为什么用字典树会MLE???
查看原帖
为什么用字典树会MLE???
706459
Go_for_itligli666666楼主2022/8/1 16:29
#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;
}
2022/8/1 16:29
加载中...