AcWing 835. Trie字符串统计 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-21 13:35:34
,
所有人可见
,
阅读 643
//idx 为节点编号,0为根节点
let idx = 0;
let children = new Array(100010);
for (let i = 0; i < children.length; i++) {
children[i] = new Int32Array(26);
}
let strCount = new Int32Array(100010);
let insert = str => {
let p = 0;//p为节点编号,从根节点开始
let codea = 'a'.charCodeAt();
for (let i = 0; i < str.length; i++) {
let u = str[i].charCodeAt() - codea;
if (!children[p][u]) children[p][u] = ++idx;//不存在则新建节点
p = children[p][u];//走过的节点编号
}
strCount[p]++;
}
let query = str => {
let p = 0;
let codea = 'a'.charCodeAt();
for (let i = 0; i < str.length; i++) {
let u = str[i].charCodeAt() - codea;
if(!children[p][u]) return 0;
p = children[p][u];
}
return strCount[p];
}
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
let m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
m = a[0];
} else if (lineIdx <= m) {
switch (line[0]) {
case 'I': {
let str = getInputStr(line)[1];
insert(str);
break;
}
case 'Q': {
let str = getInputStr(line)[1];
console.log(query(str));
break;
}
}
}
});
});