79 lines
1.8 KiB
Rust
79 lines
1.8 KiB
Rust
use std::io::{self, BufRead};
|
||
|
||
|
||
fn next(s: &Vec<char>, start: usize, end: usize) -> Vec<usize> {
|
||
let n = end - start;
|
||
let mut nxt = vec![0; n];
|
||
let mut j = 0;
|
||
for i in 1..n {
|
||
while j > 0 && s[start + i] != s[start + j] {
|
||
j = nxt[j - 1];
|
||
}
|
||
if s[start + i] == s[start + j] {
|
||
j += 1;
|
||
}
|
||
nxt[i] = j;
|
||
}
|
||
nxt
|
||
}
|
||
|
||
fn main(){
|
||
let stdin = io::stdin();
|
||
for line in stdin.lock().lines() {
|
||
let s = line.unwrap();
|
||
if s.trim().is_empty() { continue; }
|
||
|
||
let c: Vec<char> = s.trim().chars().collect();
|
||
let n = c.len();
|
||
let mut nxt = next(&c, 0, c.len());
|
||
let mut plen = -1;
|
||
|
||
//计算P的话可以直接用最长后缀算，使用KMP
|
||
for len in (1..n).rev() {
|
||
let mode: Vec<char> = c[n - len..n].to_vec();
|
||
let tmp: Vec<usize> = next(&mode, 0, mode.len());
|
||
let mut i = 0;
|
||
let mut j = 0;
|
||
while i < n - 1 {
|
||
while j > 0 && c[i] != mode[j] {
|
||
j = tmp[j - 1];
|
||
}
|
||
if c[i] == mode[j] {
|
||
j += 1;
|
||
}
|
||
if j == mode.len() {
|
||
plen = mode.len() as i32;
|
||
break;
|
||
}
|
||
if plen > 0 {
|
||
break;
|
||
}
|
||
i += 1;
|
||
}
|
||
if plen > 0 {
|
||
break;
|
||
}
|
||
}
|
||
|
||
//计算Q，用len1和len2，如果2 * qlen > len(s)，则len(Q) = 0
|
||
|
||
let mut qlen = 0;
|
||
if nxt[n - 1] > 0 {
|
||
qlen = nxt[nxt[n - 1] - 1];
|
||
}
|
||
if 2 * qlen > n {
|
||
qlen = 0;
|
||
} else {
|
||
qlen = n - 2 * qlen;
|
||
}
|
||
|
||
if plen < 0 {
|
||
plen = 0;
|
||
}
|
||
let out = qlen as i32 + plen as i32;
|
||
println!("{}", out);
|
||
|
||
//println!("qlen: {}", qlen);
|
||
//println!("plen: {}", plen);
|
||
}
|
||
} |