码蹄集2198--个数统计2
高精度*低精度+KMP求解
高精度*低精度：码蹄集2197--个数统计_sweet_Mary的博客-CSDN博客
KMP：码蹄集2176--字符串构造_sweet_Mary的博客-CSDN博客（这里只写了next数组的求解模板）
这里补上KMP的求解模板
int kmp(string a,int len_a, string b,int len_b) {int i = 0, j = 0;int temp = 0;while (i < len_a && j本题的代码：
//高精度计算+KMP
#include
#include
#include
#include
#includeusing namespace std;
int N;
string b;
//a*新来的数放入res中
int a[3010];
int res[3010];
int cnt[3010];
int next_[3010];void high_multiple(int num, int& len) {for (int i = 0; i < len; i++) {res[i] += a[i] * num;if (res[i] >= 10) {res[i + 1] += res[i] / 10;res[i] %= 10;}}while (res[len]) {if (res[len] >= 10) {res[len + 1] += res[len] / 10;res[len] %= 10;}len++;}while (res[len - 1] == 0 && len > 1) {len--;}}void find_next(int len_b) {int j = -1, i = 0;next_[0] = -1;while (i <= len_b) {if (j == -1 || b[i] == b[j]) {i++;j++;next_[i] = j;}else {j = next_[j];}}
}int kmp(int len, int len_b) {//int类型的cnt数组为文本串，string类型的b是模式串int i = 0, j = 0;int temp = 0;while (i < len) {if (j == -1 || cnt[i] == (b[j] - '0')) {i++; j++;}else {j = next_[j];}if (j == len_b) {temp++;j = next_[j];}}return temp;
}int main()
{cin >> N >> b;int len_b = b.size();int len = 1;a[0] = 1;for (int i = 1; i <= N; i++) {high_multiple(i, len);memcpy(a, res, sizeof(res));memset(res, 0, sizeof(res));}//将结果逆序存放在a数组中//将结果转变到cnt数组中for (int i = 0; i < len; i++) {cnt[i] = a[len - i - 1];}find_next(len_b);cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！