結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2019-08-22 01:00:35 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 548 ms / 2,000 ms |
コード長 | 8,408 bytes |
コンパイル時間 | 11,589 ms |
コンパイル使用メモリ | 380,604 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-11-10 00:29:52 |
合計ジャッジ時間 | 17,753 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 |
コンパイルメッセージ
warning: fields `m` and `b` are never read --> src/main.rs:142:5 | 140 | struct RollingHashRaw { | -------------- fields in this struct 141 | hash: Vec<i64>, 142 | m: usize, // len(t) | ^ 143 | b: i64, | ^ | = note: `#[warn(dead_code)]` on by default warning: method `find` is never used --> src/main.rs:188:8 | 147 | impl RollingHashRaw { | ------------------- method in this implementation ... 188 | fn find(&self, t: &[i64], from: usize) -> Option<usize> { | ^^^^ warning: field `bh_set` is never read --> src/main.rs:214:5 | 213 | struct RollingHash { | ----------- field in this struct 214 | bh_set: Vec<(i64, i64)>, | ^^^^^^ warning: method `find` is never used --> src/main.rs:231:8 | 217 | impl RollingHash { | ---------------- method in this implementation ... 231 | fn find(&self, t: &[i64], from: usize) -> Option<usize> { | ^^^^ warning: variable `S` should have a snake case name --> src/main.rs:105:9 | 105 | S: chars, | ^ 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:106:9 | 106 | M: usize, | ^ help: convert the identifier to snake case: `m` warning: variable `C` should have a snake case name --> src/main.rs:107:9 | 107 | C: [chars; M], | ^ help: convert the identifier to snake case (notice the capitalization): `c`
ソースコード
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]#[allow(unused_imports)]use std::cmp::{max, min, Ordering};#[allow(unused_imports)]use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};#[allow(unused_imports)]use std::io::{stdin, stdout, BufWriter, Write};#[allow(unused_imports)]use std::iter::FromIterator;#[allow(unused_macros)]macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }#[macro_export]macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser :ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser ,$ ( $ r ) * } } ; }#[macro_export]macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }#[macro_export]macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [$ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser :ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => {read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; }use std::io;use std::io::BufRead;use std::str;pub struct Parser<R> {reader: R,buf: Vec<u8>,pos: usize,}impl Parser<io::Empty> {pub fn from_str(s: &str) -> Parser<io::Empty> {Parser {reader: io::empty(),buf: s.as_bytes().to_vec(),pos: 0,}}}impl<R: BufRead> Parser<R> {pub fn new(reader: R) -> Parser<R> {Parser {reader: reader,buf: vec![],pos: 0,}}pub fn update_buf(&mut self) {self.buf.clear();self.pos = 0;loop {let (len, complete) = {let buf2 = self.reader.fill_buf().unwrap();self.buf.extend_from_slice(buf2);let len = buf2.len();if len == 0 {break;}(len, buf2[len - 1] <= 0x20)};self.reader.consume(len);if complete {break;}}}pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {loop {let mut begin = self.pos;while begin < self.buf.len() && (self.buf[begin] <= 0x20) {begin += 1;}let mut end = begin;while end < self.buf.len() && (self.buf[end] > 0x20) {end += 1;}if begin != self.buf.len() {self.pos = end;return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();} else {self.update_buf();}}}}#[allow(unused_macros)]macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }#[doc = " https://github.com/hatoo/competitive-rust-snippets"]const BIG_STACK_SIZE: bool = true;#[allow(dead_code)]fn main() {use std::thread;if BIG_STACK_SIZE {thread::Builder::new().stack_size(32 * 1024 * 1024).name("solve".into()).spawn(solve).unwrap().join().unwrap();} else {solve();}}fn ctoi(c: char) -> i64 {c as i64 - 'A' as i64}fn solve() {input! {S: chars,M: usize,C: [chars; M],}let s: Vec<i64> = S.iter().map(|&x| ctoi(x)).collect();let mut rhs = vec![];for m in 1..11 {if s.len() < m { continue; }let rh = RollingHash::new(&s, m); // O(|S|)rhs.push(rh);}let mut ans = 0;for c in C { // O(M)let c: Vec<i64> = c.iter().map(|&x| ctoi(x)).collect();if c.len() > s.len() { continue; }let rh = &rhs[c.len()-1];let res = rh.find_all(&c); // O(|S|+|C|) = O(|S|)ans += res.len();}println!("{}", ans);}pub fn gcd(a: i64, b: i64) -> i64 {if b == 0 {a} else {gcd(b, a % b)}}pub fn modp(x: i64, p: i64) -> i64 {let mut res = x;res %= p;(res+p) % p}struct RollingHashRaw {hash: Vec<i64>,m: usize, // len(t)b: i64,h: i64,b_pow: Vec<i64>, // b^0 .., b^m}impl RollingHashRaw {fn calc_hash(s: &[i64], m: usize, b_pow: &[i64], h: i64) -> i64 {let mut res = 0;for i in 0..m {res += s[i] * b_pow[m-1-i];res %= h;}res}fn new(s: &[i64], m: usize, b: i64, h: i64) -> RollingHashRaw {let n = s.len();assert_eq!(gcd(b, h), 1);assert!(n>=m);let mut b_pow = vec![1];let mut acc = 1;for _ in 1..m+1 {acc *= b;acc %= h;b_pow.push(acc);}let mut hash = vec![];let mut cur_hash = Self::calc_hash(&s, m, &b_pow, h);hash.push(cur_hash);for i in 1..n+1-m {let k = i-1;cur_hash *= b;cur_hash = modp(cur_hash, h);cur_hash -= s[k] * b_pow[m];cur_hash = modp(cur_hash, h);cur_hash += s[k+m];cur_hash = modp(cur_hash, h);hash.push(cur_hash);}RollingHashRaw {hash: hash,m: m,b: b,h: h,b_pow: b_pow,}}fn find(&self, t: &[i64], from: usize) -> Option<usize> {let th = Self::calc_hash(t, t.len(), &self.b_pow, self.h);let mut res = None;for k in from..self.hash.len() {if self.hash[k] == th {res = Some(k);break;}}res}fn find_all(&self, t: &[i64]) -> Vec<usize> {let th = Self::calc_hash(t, t.len(), &self.b_pow, self.h);let mut res = vec![];for k in 0..self.hash.len() {if self.hash[k] == th {res.push(k);}}res}fn hash_len(&self) -> usize {self.hash.len()}}struct RollingHash {bh_set: Vec<(i64, i64)>,rhs: Vec<RollingHashRaw>,}impl RollingHash {fn new(s: &[i64], m: usize) -> RollingHash {let bh_set = vec![(1009, 1_000_000_007), (1007, 1_000_000_009)];let mut rhs = vec![];for i in 0..bh_set.len() {let (b,h) = bh_set[i];rhs.push(RollingHashRaw::new(s, m, b, h));}RollingHash {bh_set,rhs,}}// O(m+n)fn find(&self, t: &[i64], from: usize) -> Option<usize> {let mut results = vec![];for rh in &self.rhs {results.push(rh.find(t, from));}let base = results[0];for result in results {if result != base {return None;}}base}// O(m+n)fn find_all(&self, t: &[i64]) -> Vec<usize> {let mut results = vec![];for rh in &self.rhs {results.push(rh.find_all(t));}let mut cnt = vec![0; self.rhs[0].hash_len()];for result in results {for i in result {cnt[i] += 1;}}let mut res = vec![];for i in 0..cnt.len() {if cnt[i] == self.rhs.len() {res.push(i);}}res}}