Given a string of length n consisting of digits [0-9], count the number of ways the given string can be split into prime numbers. The digits must remain in the order given and the entire string must be used. Each number must be in the range 2 to 10⁸ inclusive, and may not contain leading zeros. Since the answer can be large, return the answer modulo 10⁹ + 7.
Note: The trailing string does not contain leading zeros.
Example: s = "11375" — can be split into primes 3 different ways: [11, 37, 5], [11, 3, 7, 5], [113, 7, 5].
解法
在字符串上 DP：f[i] 表示把 s[0..i-1] 切成质数的方案数。转移：枚举末段 s[j..i-1] 长度 ≤ 9(值 ≤ 10⁸ 至多 9 位)，若是无前导零的质数则 f[i] += f[j]。最坏复杂度 O(n × 9 × sqrt(10⁸))，瓶颈在素性判断。
from sympy import isprime
MOD = 10**9 + 7
def countPrimeStrings(s):
n = len(s)
f = [0] * (n + 1)
f[0] = 1
for i in range(1, n + 1):
for j in range(max(0, i - 9), i):
sub = s[j:i]
if len(sub) > 1 and sub[0] == '0': continue
v = int(sub)
if 2 <= v <= 10**8 and isprime(v):
f[i] = (f[i] + f[j]) % MOD
return f[n]class Solution {
static final int MOD = 1_000_000_007;
public int countPrimeStrings(String s) {
int n = s.length();
long[] f = new long[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = Math.max(0, i - 9); j < i; j++) {
if (i - j > 1 && s.charAt(j) == '0') continue;
long v = Long.parseLong(s.substring(j, i));
if (v >= 2 && v <= 100_000_000L && isPrime(v)) f[i] = (f[i] + f[j]) % MOD;
}
}
return (int) f[n];
}
private boolean isPrime(long x) {
if (x < 2) return false;
for (long i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
}
}int countPrimeStrings(string s) {
const int MOD = 1e9 + 7;
auto isPrime = [](long long x) {
if (x < 2) return false;
for (long long i = 2; i * i <= x; ++i) if (x % i == 0) return false;
return true;
};
int n = s.size();
vector<long long> f(n + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = max(0, i - 9); j < i; ++j) {
if (i - j > 1 && s[j] == '0') continue;
long long v = stoll(s.substr(j, i - j));
if (v >= 2 && v <= 100000000LL && isPrime(v)) f[i] = (f[i] + f[j]) % MOD;
}
}
return f[n];
}Given three strings text, prefixString, and suffixString, find:
prefixScore: the longest substring oftextmatching the end ofprefixString.suffixScore: the longest substring oftextmatching the beginning ofsuffixString.
Sum the lengths of the two strings to get the textScore. The substring of text that begins with the matching prefix and ends with matching suffix, and has the highest textScore, is the correct value to return. If there are other substrings with equal textScore, return the lexicographically lowest substring.
Note: if the prefix and suffix overlap, return only the substring of text, not prefix + suffix.
解法
对 text 中每个起点 i 求最长前缀匹配长度(text[i..i+k-1] == prefixString[-k:] 的最大 k)；同理对每个终点 j 求最长后缀匹配(text[j-k+1..j] == suffixString[0..k-1])。在不重叠的前缀/后缀端点上配对使得总长最大，平局取字典序最小子串。复杂度 O(|text| × min(|prefix|,|suffix|))。
def getSubstring(text, prefixString, suffixString):
n = len(text)
pref_match = [0] * n
for i in range(n):
k = 0
while k < min(len(prefixString), n - i) + 1:
if k == 0 or text[i:i+k] == prefixString[-k:]:
k += 1
else:
break
pref_match[i] = k - 1
suf_match = [0] * n
for i in range(n):
k = 0
while k < min(len(suffixString), i + 1) + 1:
if k == 0 or text[i-k+1:i+1] == suffixString[:k]:
k += 1
else:
break
suf_match[i] = k - 1
best_score, best_str = -1, ""
for l in range(n):
for r in range(l, n):
ps, ss = pref_match[l], suf_match[r]
if ps == 0 or ss == 0: continue
if l + ps - 1 > r or r - ss + 1 < l: continue
score = ps + ss
sub = text[l:r+1]
if score > best_score or (score == best_score and sub < best_str):
best_score, best_str = score, sub
return best_strclass Solution {
public String getSubstring(String text, String pref, String suf) {
int n = text.length(); String best = ""; int bestScore = -1;
for (int l = 0; l < n; l++) for (int r = l; r < n; r++) {
int ps = 0, ss = 0;
for (int k = 1; k <= Math.min(pref.length(), r - l + 1); k++)
if (text.substring(l, l + k).equals(pref.substring(pref.length() - k))) ps = k;
for (int k = 1; k <= Math.min(suf.length(), r - l + 1); k++)
if (text.substring(r - k + 1, r + 1).equals(suf.substring(0, k))) ss = k;
if (ps == 0 || ss == 0) continue;
int sc = ps + ss;
String sub = text.substring(l, r + 1);
if (sc > bestScore || (sc == bestScore && sub.compareTo(best) < 0)) { bestScore = sc; best = sub; }
}
return best;
}
}string getSubstring(string text, string pref, string suf) {
int n = text.size();
string best = ""; int bestScore = -1;
for (int l = 0; l < n; ++l) for (int r = l; r < n; ++r) {
int ps = 0, ss = 0;
for (int k = 1; k <= min((int)pref.size(), r - l + 1); ++k)
if (text.substr(l, k) == pref.substr(pref.size() - k)) ps = k;
for (int k = 1; k <= min((int)suf.size(), r - l + 1); ++k)
if (text.substr(r - k + 1, k) == suf.substr(0, k)) ss = k;
if (ps == 0 || ss == 0) continue;
int sc = ps + ss;
string sub = text.substr(l, r - l + 1);
if (sc > bestScore || (sc == bestScore && sub < best)) { bestScore = sc; best = sub; }
}
return best;
}The NLP enthusiasts of Hackerland are working on a string transformation algorithm. In a single operation, a string s can be transformed into another string by removing a suffix of the string and adding the removed suffix in front of the remaining string. For example, the string "abcd" can be transformed to "cdab" by removing the suffix "cd" and adding it to the front of the remaining string "ab".
Given two strings src and target of lowercase English characters and an integer k, find the number of ways to transform the string src to the string target using the given algorithm in exactly k steps. Since the answer can be large, report it modulo 10⁹ + 7.
Two ways are considered different if the sequence of indices chosen for breaking the suffix is different at 1 or more steps for the two ways.
解法
每步操作都是 src 的循环旋转。预处理 t = src 的旋转中等于 target 的个数。设 f[k] 为走 k 步后停在等于 target 的旋转上的方案数，g[k] 为停在不等的方案数。递推：
f[k] = f[k-1] * (t - 1) + g[k-1] * t
g[k] = f[k-1] * (n - t) + g[k-1] * (n - 1 - t)复杂度 O(n + k)。
MOD = 10**9 + 7
def get_num_ways(src, target, k):
n = len(src)
t = sum(1 for i in range(n) if (src + src)[i:i+n] == target)
f, g = (1, 0) if src == target else (0, 1)
for _ in range(k):
f, g = (f * (t - 1) + g * t) % MOD, (f * (n - t) + g * (n - 1 - t)) % MOD
return fclass Solution {
static final int MOD = 1_000_000_007;
public int getNumWays(String src, String target, int k) {
int n = src.length();
String ss = src + src;
int t = 0;
for (int i = 0; i < n; i++) if (ss.substring(i, i + n).equals(target)) t++;
long f = src.equals(target) ? 1 : 0;
long g = src.equals(target) ? 0 : 1;
for (int i = 0; i < k; i++) {
long nf = (f * ((t - 1 + MOD) % MOD) + g * t) % MOD;
long ng = (f * (n - t) + g * ((n - 1 - t + MOD) % MOD)) % MOD;
f = nf; g = ng;
}
return (int) f;
}
}int getNumWays(string src, string target, int k) {
const int MOD = 1e9 + 7;
int n = src.size();
string ss = src + src;
int t = 0;
for (int i = 0; i < n; ++i) if (ss.substr(i, n) == target) ++t;
long long f = (src == target) ? 1 : 0, g = (src == target) ? 0 : 1;
for (int i = 0; i < k; ++i) {
long long nf = (f * (t - 1 + MOD) + g * t) % MOD;
long long ng = (f * (n - t) + g * (n - 1 - t + MOD)) % MOD;
f = nf; g = ng;
}
return f;
}