#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
- 粉丝: 2677
- 资源: 631
最新资源
- 基于Java语言的随机点名系统设计源码
- 基于Spring Boot框架的餐厅配送系统设计源码
- 基于Python Neo4j的藏区健康科普手册知识图谱问答系统设计源码
- 基于Java和前端技术的学籍管理JSP页面设计源码
- 自动驾驶不同工况避障模型(perscan、simulink、carsim联合仿真),能够避开预设的(静态)障碍物
- 基于C++语言的简易航班管理系统设计源码
- SS-SP型磁耦合谐振无线电能传输移相控制仿真复现文献 复现一篇2018年的英文文献 控制描述:采用负载估算和移相控制策略
- 基于Java与JavaScript的UART艺术展览信息网站设计源码
- 直流电压源+双向Buck-Boost DCDC变器+负载+锂离子电池+控制系统,Simulink仿真模型 有两种工作模式: 1
- 基于IntelliJ IDEA的Java项目Git集成与版本控制设计源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈