0w1

KMP

CFR 825 F. String Compression

Problem Description: Given string S, find the minimum length of its running length encoding.Constraints: 1 ≤ len(S) ≤ 8000Solution: dp[i]: answer for S[0...i] dp[j] = min(dp[i] + cost(i, j) for i in 0...j) kmp[i]: maximum length of common …

CFR 526 D. Om Nom and Necklace ( KMP, Periodic )

Problem - D - Codeforces題意: 給長度 N 的字串,以及定數 K。 對於 i = [ 0 .. N - 1 ],問是否存在字串 A 和 B,使得 A + B + A + B .. + A = S[ 0 .. i ],其中 A 重複 K + 1 次,B 重複 K 次。 A, B 可為空字串。制約: 1 ≤ N, K ≤ 1e6解法: KMP 真是…

IOICJ 31 Repeated String ( KMP )

Problem Description: Given string S, find A with minimum length, such that S is equivalent to A being concatenated several times.Constraints: 1≤T≤100 1≤|S|≤1e5 TL: 1000 msSample Input: 3 ababab aaabaaab aaabaaaSample Output: 2 4 7Solution:…