I'm try to solve string searching problem using Rust on this site, I've tried to "translate" my previous accepted code from C++ to Rust. For the C++ answer, I can pass all of the testcase.
But, when I use Rust, I can't pass the upper corner testcase (find 10000 length string in 1000000 length string) and I keep getting Time Limit Exceed even when I try use someone algorithm.
So am I doing something wrong for the Rust code? Or is this is not a good problem for Rust?
This is my code in C++:
#include <iostream>
//#include <chrono>
void computeLPSArray(std::string * pattern, int M, int * lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if ((*pattern)[i] == (*pattern)[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(std::string *pattern, std::string *string) {
int M = pattern->length();
int N = string->length();
int lps[M];
computeLPSArray(pattern, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if ((*pattern)[j] == (*string)[i]) {
j++;
i++;
}
if (j == M) {
std::cout << i - j << std::endl;
j = lps[j - 1];
}else if (i < N && (*pattern)[j] != (*string)[i]) {
if (j != 0){
j = lps[j - 1];
}else{
i = i + 1;
}
}
}
}
int main() {
std::string pattern, string;
getline(std::cin, string);
getline(std::cin, pattern);
//std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
KMPSearch(&pattern, &string);
//std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
//std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "micros" <<std::endl;
return 0;
}
My Rust code:
fn read_line() -> String {
let mut return_ = format!("");
std::io::stdin().read_line(&mut return_).ok();
return_.pop();
return_
}
fn main() {
let string: Vec<char> = read_line().chars().collect();
let pattern: Vec<char> = read_line().chars().collect();
//let start = std::time::Instant::now();
kmp(&string, &pattern);
//println!("{:?}", start.elapsed());
}
fn lps(pattern: &Vec<char>, m: usize, mut kmp: Vec<usize>) -> Vec<usize> {
let mut len: usize = 0;
kmp[0] = 0;
let mut i: usize = 1;
while i < m {
if pattern[i] == pattern[len] {
len = len + 1;
kmp[i] = len;
i = i + 1;
} else {
if len != 0 {
len = kmp[len - 1];
} else {
kmp[i] = 0;
i = i + 1;
}
}
}
kmp
}
fn kmp(string: &Vec<char>, pattern: &Vec<char>) -> () {
let n = string.len();
let m = pattern.len();
let kmp = lps(&pattern, m, vec![0usize; m]);
let mut i: usize = 0;
let mut j: usize = 0;
while i < n {
if pattern[j] == string[i] {
i = i + 1;
j = j + 1;
}
if j == m {
println!("{:?}", i - j);
j = kmp[j - 1];
} else if i < n && pattern[j] != string[i] {
if j != 0 {
j = kmp[j - 1];
} else {
i = i + 1;
}
}
}
}
Solved code:
fn read_line() -> String {
let mut return_ = format!("");
std::io::stdin().read_line(&mut return_).ok();
return_.pop();
return_
}
fn main() {
let string: Vec<u8> = read_line().as_bytes().to_vec();
let pattern: Vec<u8> = read_line().as_bytes().to_vec();
//let start = std::time::Instant::now();
kmp(&string, &pattern);
//println!("{:?}", start.elapsed());
}
fn kmp_table(pattern: &Vec<u8>, m: usize, mut kmp: Vec<usize>) -> Vec<usize> {
let mut len: usize = 0;
kmp[0] = 0;
let mut i: usize = 1;
while i < m {
if pattern[i] == pattern[len] {
len = len + 1;
kmp[i] = len;
i = i + 1;
} else {
if len != 0 {
len = kmp[len - 1];
} else {
kmp[i] = 0;
i = i + 1;
}
}
}
kmp
}
fn kmp(string: &Vec<u8>, pattern: &Vec<u8>) -> () {
let mut out: String = String::new();
let n = string.len();
let m = pattern.len();
let kmp = kmp_table(&pattern, m, vec![0usize; m]);
let mut i: usize = 0;
let mut j: usize = 0;
while i < n {
if pattern[j] == string[i] {
i = i + 1;
j = j + 1;
}
if j == m {
out.push_str(&(i - j).to_string());
out.push('\n');
j = kmp[j - 1];
} else if i < n && pattern[j] != string[i] {
if j != 0 {
j = kmp[j - 1];
} else {
i = i + 1;
}
}
}
print!("{}", out);
}
.
. Besides potentially killing loop optimizations, C# has the added issue of needing a memory load to get an array’s length - if that misses in cache, you stall badly. Rust is better in this regard because sliced have the length in the fat ptr, which will likely be kept in a register or at worst, spilled to a stack slot.