AcWing 841. 字符串哈希 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-24 23:03:24
,
所有人可见
,
阅读 934
const P = 131n;//mod = 2^64 自动溢出取模
let hash = new BigUint64Array(100010);
let power = new BigUint64Array(100010);
power[0] = 1n;
let initHash = str => {
for (let i = 1; i < str.length; i++) {
hash[i] = hash[i - 1] * P + BigInt.asUintN(64, BigInt(str[i].charCodeAt(0)));
power[i] = power[i - 1] * P;
}
}
let subHash = (l, r) => {
return BigInt.asUintN(64,hash[r] - hash[l - 1] * power[r - l + 1]);
}
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 n = 0, m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
n = a[0], m = a[1];
} else if (lineIdx === 1) {
initHash('*' + getInputStr(line)[0]);
} else if (lineIdx <= m + 1) {
let arr = getInputNums(line);
let a = subHash(arr[0], arr[1]);
let b = subHash(arr[2], arr[3]);
if (a === b) {
console.log('Yes');
} else {
console.log('No');
}
}
});
});