• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

[AcWIng 835] Trie字符串统计


Recommended Posts

image

image

单击以查看代码#includeiostream。

使用命名空间std

const int N=1e5 10

int son[N][26],cnt[N],idx

char str[N];

void insert(字符串[])

{

int p=0;

for(int I=0;str;i ) {

int u=str-' a ';

如果(!son[p])son[p]=idx;

p=son[p]

}

CNT[p];

}

int查询(字符串[])

{

int p=0;

for(int I=0;str;i ) {

int u=str-' a ';

如果(!son[p])返回0;

p=son[p]

}

return CNT[p];

}

int main()

{

int n;

CIN n;

while (n - ) {

char op

cin海峡;

if(op==' I ')insert(str);

else if(op==' Q ')cout query(str)endl;

}

返回0;

}

字典树适合插入和查询大小写字符串;

字母‘a’-‘z’用数字‘0’-‘25’表示;

使用数组存储字典树。数组下标为0的节点既是根节点又是空节点。

son[ i ][ j]中的I代表字典树的层数(也可以理解为字符串的第I个位置),j代表这个位置的字符,son[ i ][ j]的值是数组中下一个节点的位置。

Cnt用于记录以p位置结尾的字符出现的次数;

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now