Appearance
大整数乘法(高精度乘法)
假设有两个整数
计算
提取
从右往左,逢
这样就能得到
多项式乘法由 FFT 进行。如果
整数乘法和多项式乘法具有高度的相似性。
一个整数可以分解为它的位值的和。例如,整数
设
设
可以看出整数乘法和多项式乘法基本是同构的。整数乘法在最后一步需要额外处理进位。
模板
cpp
// put FFT algorithm template here
vector<Comp> string_to_vector(const string& s) {
vector<Comp> result;
for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {
result.push_back(*rit - '0');
}
return result;
}
string vector_to_string(const vector<Comp>& v) {
string result;
for (const Comp& c : v) {
result += to_string(int(c.real())) + " ";
}
return result;
}
string upgrade(vector<Comp>& a) {
string result;
int carry = 0;
for (auto i : a) {
int num = int(real(i) + 0.5) + carry;
carry = num / 10;
result += (num % 10) + '0';
}
while (!result.empty() && result.back() == '0') {
result.pop_back();
}
reverse(result.begin(), result.end());
return result.empty() ? "0" : result;
}
string multiply_big_integers(const string& s1, const string& s2) {
vector<Comp> a = string_to_vector(s1);
vector<Comp> b = string_to_vector(s2);
vector<Comp> c = multiply(a, b);
return vector_to_string(c);
}
int main() {
string num1, num2;
cin >> num1 >> num2;
string product = multiply_big_integers(num1, num2);
cout << product << endl;
return 0;
}
朴素字符串匹配
设有两个字符串
该问题可使用 FFT 在
约定
首先将
容易发现
进而构造
因此可以利用
展开
将数组
分析该式的三项:
可以通过前缀和技巧实现 预处理, 查询; 是常数,可以直接 预处理; 是卷积式,可以通过 FFT 实现 预处理, 查询。
对于第 3 项,更具体地说:
构造多项式
利用 FFT 可以
依次计算
用 FFT 实现的字符串匹配,其效率并不是最优的,并且常数很大。
KMP 可以在
模板
cpp
// put FFT algorithm template here
vector<int> stringMatchingFFT(const string& text, const string& pattern) {
int n = text.size(), m = pattern.size();
vector<Comp> A(n), B(m);
long long sum_AA[n], sum_BB = 0;
for (int i = 0; i < n; i ++) {
int value = text[i] - 'a' + 1;
A[i] = value;
sum_AA[i] = value * value;
if (i) {
sum_AA[i] += sum_AA[i - 1];
}
}
for (int i = 0; i < m; i ++) {
int value = pattern[i] - 'a' + 1;
B[m - i - 1] = value;
sum_BB += value * value;
}
vector<Comp> C = multiply(A, B);
vector<int> matches;
for (int i = 0; i <= n - m; i ++) {
long long
part1 = sum_AA[i + m - 1] - (i ? sum_AA[i - 1] : 0),
part2 = sum_BB,
part3 = C[i + m - 1].real();
if (part1 + part2 - 2 * part3 == 0)
matches.push_back(i);
}
return matches;
}
int main() {
string text, pattern;
cin >> text >> pattern;
vector<int> matches = stringMatchingFFT(text, pattern);
cout << matches.size() << "\n";
for (int i : matches) cout << i << " ";
cout << "\n";
return 0;
}
带通配符的字符串匹配
设有两个字符串
令通配符
构造多项式
是 中 前的系数; 是 中 前的系数; 是 中 前的系数。
进行三次 FFT 即可。
模板
cpp
// put FFT algorithm template here
vector<int> stringMatchingFFT(const string& text, string pattern) {
int n = text.size(), m = pattern.size();
vector<Comp> A1, A2, A3, B1, B2, B3;
for (auto i : text) {
int value = i == '*' ? 0 : i - 'a' + 1;
A1.push_back(value);
A2.push_back(value * value);
A3.push_back(value * value * value);
}
reverse(pattern.begin(), pattern.end());
for (auto i : pattern) {
int value = i == '*' ? 0 : i - 'a' + 1;
B1.push_back(value);
B2.push_back(value * value);
B3.push_back(value * value * value);
}
vector<Comp> part1 = multiply(A3, B1);
vector<Comp> part2 = multiply(A1, B3);
vector<Comp> part3 = multiply(A2, B2);
vector<int> matches;
for (int i = 0; i <= n - m; i ++) {
if (part1[i + m - 1].real() + part2[i + m - 1].real() - part3[i + m - 1].real() * 2 == 0)
matches.push_back(i);
}
return matches;
}
int main() {
string text, pattern;
cin >> text >> pattern;
vector<int> matches = stringMatchingFFT(text, pattern);
cout << matches.size() << "\n";
for (int i : matches) cout << i << " ";
cout << "\n";
return 0;
}