結果
| 問題 |
No.430 文字列検索
|
| コンテスト | |
| ユーザー |
 pianoneko
|
| 提出日時 | 2019-09-22 00:50:40 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,511 bytes |
| コンパイル時間 | 13,794 ms |
| コンパイル使用メモリ | 379,512 KB |
| 実行使用メモリ | 10,496 KB |
| 最終ジャッジ日時 | 2024-11-10 00:33:45 |
| 合計ジャッジ時間 | 15,362 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 4 |
| other | AC * 1 TLE * 1 -- * 12 |
コンパイルメッセージ
warning: unused import: `std::io::BufRead`
--> src/main.rs:2:5
|
2 | use std::io::BufRead;
| ^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused imports: `Add`, `Div`, `Mul`, `Sub`
--> src/main.rs:4:16
|
4 | use std::ops::{Add, Div, Mul, Sub};
| ^^^ ^^^ ^^^ ^^^
warning: function `read` is never used
--> src/main.rs:22:4
|
22 | fn read<T: FromStr>() -> T {
| ^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: static `MOD` is never used
--> src/main.rs:144:8
|
144 | static MOD: i64 = 1e9 as i64 + 7;
| ^^^
warning: variable `S` should have a snake case name
--> src/main.rs:185:12
|
185 | input!(S: String, M: usize);
| ^ help: convert the identifier to snake case (notice the capitalization): `s`
|
= note: `#[warn(non_snake_case)]` on by default
warning: variable `M` should have a snake case name
--> src/main.rs:185:23
|
185 | input!(S: String, M: usize);
| ^ help: convert the identifier to snake case: `m`
ソースコード
use std::fmt::Debug;
use std::io::BufRead;
use std::io::{stdin, Read};
use std::ops::{Add, Div, Mul, Sub};
use std::str::FromStr;
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);
impl<T: PartialOrd> PartialOrd for Rev<T> {
fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl<T: Ord> Ord for Rev<T> {
fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {
other.0.cmp(&self.0)
}
}
fn read<T: FromStr>() -> T {
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.expect("failed to read char") as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().expect("failed to parse token")
}
macro_rules! read {
(($($t:tt),*)) => {
( $(read!($t)),* )
};
([[$t:tt; $len1:expr]; $len2:expr]) => {
(0..$len2).map(|_| read!([$t; $len1])).collect::<Vec<_>>()
};
([$t:tt; $len:expr]) => {
(0..$len).map(|_| read!($t)).collect::<Vec<_>>()
};
(chars) => {
read!(String).chars().collect::<Vec<char>>()
};
(usize1) => {
read!(usize) - 1
};
($t:ty) => {{
let stdin = stdin();
let stdin = stdin.lock();
let token: String = stdin
.bytes()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse::<$t>().unwrap()
}};
}
macro_rules! input {
(mut $name:ident: $t:tt, $($r:tt)*) => {
let mut $name = read!($t);
input!($($r)*);
};
(mut $name:ident: $t:tt) => {
let mut $name = read!($t);
};
($name:ident: $t:tt, $($r:tt)*) => {
let $name = read!($t);
input!($($r)*);
};
($name:ident: $t:tt) => {
let $name = read!($t);
};
}
trait VecExt {
fn cumulation(&self) -> Vec<i64>;
fn cumulation_query(&self, a: &usize, b: &usize) -> i64;
}
impl VecExt for Vec<i64> {
fn cumulation(&self) -> Vec<i64> {
let mut vec = vec![0; self.len() + 1];
for i in 0..self.len() {
vec[i + 1] = self[i] + vec[i];
}
return vec;
}
fn cumulation_query(&self, left: &usize, right: &usize) -> i64 {
return self[*right] - self[*left];
}
}
trait SliceExt<T> {
fn lower_bound(&self, x: &T) -> usize;
fn upper_bound(&self, x: &T) -> usize;
}
impl<T: Ord> SliceExt<T> for [T] {
fn lower_bound(&self, x: &T) -> usize {
let mut ng = -1;
let mut ok = self.len() as i64;
while (ok - ng).abs() > 1 {
let mid = (ok + ng) / 2;
if self[mid as usize] >= *x {
ok = mid;
} else {
ng = mid;
}
}
return ok as usize;
}
fn upper_bound(&self, x: &T) -> usize {
let mut ng = -1;
let mut ok = self.len() as i64;
while (ok - ng).abs() > 1 {
let mid = (ok + ng) / 2;
if self[mid as usize] > *x {
ok = mid;
} else {
ng = mid;
}
}
return ok as usize;
}
}
static MOD: i64 = 1e9 as i64 + 7;
pub struct RollingHash {
hash_pow_list: Vec<(i64, Vec<(i64, i64)>)>,
}
impl RollingHash {
pub fn new(s: &[i64]) -> RollingHash {
RollingHash::with_base_mod_pairs(s, &[(1009, 1_000_000_007), (9973, 999_999_937)])
}
pub fn with_base_mod_pairs(s: &[i64], base_mod_pairs: &[(i64, i64)]) -> RollingHash {
let hp_list = base_mod_pairs
.iter()
.map(|&(base, m)| {
let mut hp = Vec::with_capacity(s.len() + 1);
hp.push((0, 1));
for (i, &x) in s.iter().enumerate() {
let (h, p) = hp[i];
hp.push(((h + x) * base % m, p * base % m));
}
(m, hp)
})
.collect();
RollingHash {
hash_pow_list: hp_list,
}
}
pub fn get(&self, l: usize, r: usize) -> i64 {
self.hash_pow_list
.iter()
.map(|(m, hp)| (hp[r].0 + m - hp[l].0 * hp[r - l].1 % m) % m)
.fold(0, |a, b| a ^ b)
}
pub fn len(&self) -> usize {
self.hash_pow_list
.first()
.map(|v| v.1.len() - 1)
.unwrap_or(0)
}
}
fn main() {
input!(S: String, M: usize);
use std::collections::BTreeMap;
let mut map: BTreeMap<String, usize> = BTreeMap::new();
let tmp: Vec<i64> = S.chars().map(|c| c as i64).collect();
let rh = RollingHash::new(&tmp);
let mut ans = 0;
for _ in 0..M {
input!(c: String);
let cs: Vec<i64> = c.chars().map(|c| c as i64).collect();
let c_rh = RollingHash::new(&cs);
if cs.len() > tmp.len() {
continue;
}
match map.get(&c) {
None => {
let mut count = 0;
for i in 0..tmp.len() - cs.len() + 1 {
if rh.get(i, i + cs.len()) == c_rh.get(0, cs.len()) {
count += 1;
}
}
map.insert(c, count);
ans += count;
}
Some(count) => {
ans += count;
}
}
}
println!("{}", ans);
}