题目:
题解:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>#define MMAX(a, b) ((a) > (b)? (a) : (b))
#define MMIN(a, b) ((a) < (b)? (a) : (b))//【算法思路】字符串。典型的双字符串循环节问题。
// s1: |abaacdbac | abaacdbac | abaacdbac | abaacdbac | abaacdbac | abaacdbac
// s2: |a d c b d|a d c b d|a b c b d|
// s2_idx: |0 |3 |1 |3
// s2_cnt: |0 |0 |1 |1
//--------------------------------------------------------------------------------
// s1_cnt |0 |1 |2 |3 |4 |5
int getMaxRepetitions(char * s1, int n1, char * s2, int n2){if(n1 == 0) {return 0;}int slen1 = strlen(s1);int slen2 = strlen(s2);//极限情况,最多重复slen2 +1可以遇到重复int *s2_idxs = (int *)calloc(slen2 + 1, sizeof(int));int *s2_cnts = (int *)calloc(slen2 + 1, sizeof(int));int s2_idx = 0;int s2_cnt = 0;//查找循环节for(int i = 0; i < n1; i++) {//完成在s1内的一轮查找for(int j = 0; j < slen1; j++) {if(s1[j] == s2[s2_idx]) {s2_cnt = s2_idx == slen2 - 1? s2_cnt + 1 : s2_cnt;s2_idx = s2_idx == slen2 - 1? 0 : s2_idx + 1;}}//进行一次记录s2_idxs[i] = s2_idx;s2_cnts[i] = s2_cnt;//在0~i-1的范围内,查找循环节for(int j = 0; j < i; j++) {if(s2_idxs[j] == s2_idxs[i]) {//在循环节之前循环的次数//int pre_cnt = s2_cnts[j];//循环节中的s2的个数乘以循环次数int core_cnt = (s2_cnts[i] - s2_cnts[j]) * ((n1 - 1 - j) / (i - j));//将剩余的s1的循环个数加到前面,计算除循环节外的个数int pre_and_post_cnt = s2_cnts[j + ((n1 - 1 - j) % (i - j))];return (core_cnt + pre_and_post_cnt) / n2;}}}return s2_cnts[n1 - 1] / n2;
}