#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* sliding window pattern
* while (r < size) {
* // check target condition
* while (target_condition) {
* // calculate minimum length
* // iterate left indicator
* }
* // iterate right indicator
* }
*/
static char *minWindow(char *s, char *t)
{
int i, j, count[256] = { 0 };
int slen = strlen(s);
int tlen = strlen(t);
/* edges of sliding window */
int l = 0, r = 0;
int min_len = slen + 1;
int start = 0;
int len = 0;
for (i = 0; i < tlen; i++) {
count[t[i]]++;
}
while (r < slen) {
if (--count[s[r++]] >= 0) {
/* pattern found */
len++;
}
while (len >= tlen) {
if (r - l < min_len) {
min_len = r - l;
start = l;
}
/* Chars with negative count are not included in the pattern string */
if (++count[s[l++]] > 0) {
len--;
}
}
}
char *result;
if (min_len <= slen) {
result = malloc(min_len + 1);
memcpy(result, s + start, min_len);
result[min_len] = '\0';
} else {
result = "";
}
return result;
}
int main(int argc, char **argv)
{
if (argc != 3) {
fprintf(stderr, "Usage: ./test string pattern\n");
exit(-1);
}
printf("Answer: %s\n", minWindow(argv[1], argv[2]));
return 0;
}
DdddJMs__135
- 粉丝: 3129
- 资源: 754
最新资源
- 【年度培训】培训效果评估汇总表行政人事CLUB.xlsx
- 【年度培训】培训管理规范-培训管理总结行政人事CLUB.xlsx
- 【年度培训】培训成效分析图表行政人事CLUB.xlsx
- 【年度培训】培训效果评分标准行政人事CLUB.xlsx
- 【年度培训】年度培训计划记录表行政人事CLUB.xlsx
- 【年度培训】行政类专业化培训计划行政人事CLUB.xlsx
- 【年度培训】培训分析表.xls
- 【年度培训】20XX年度培训计划表行政人事CLUB.xlsx
- 【年度培训】公司内部讲师培训效果评分表行政人事CLUB.xlsx
- 【年度培训】年度培训计划表行政人事CLUB.xlsx
- 【年度培训】行政部年度培训需求计划表范例行政人事CLUB.xls
- 【年度培训】行政岗位新人入职培训计划行政人事CLUB.xls
- 【年度培训】行政年度培训计划表行政人事CLUB.xls
- 【年度培训】行政部岗前培训课程表行政人事CLUB.xls
- 【年度培训】行政部岗前培训一览表行政人事CLUB.xls
- 【年度培训】公司年度培训计划表.xls
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈