阅读量:0
这也许是双指针技巧的最⾼境界了，如果掌握了此算法，可以解决⼀⼤类⼦字符串匹配的问题
原理
1、我们在字符串 S 中使⽤双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为⼀个「窗⼝」。
2、我们先不断地增加 right 指针扩⼤窗⼝ [left, right]，直到窗⼝中的字符串 符合要求（包含了 T 中的所有字符）。
3、此时，我们停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left, right]，直到窗⼝中的字符串不再符合要求（不包含 T 中的所有字符了）。 同时，每次增加 left，我们都要更新⼀轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
代码
#include <stdio.h> const char* matchString(const char* content, const char* sub) { // 数据初始化 size_t size = strlen(content); size_t sub_size = strlen(sub); int flag[256] = {0}; // 字符数统计 // 搜索区间 const char* begin = content; const char* end = content + size; // 双指针动态滑动窗口 const char* _left = begin; const char* right = begin; // 滑动匹配 for(;right < end; ++right) { ++flag[*right]; // 窗口内字符数统计 // 缩小窗口，寻找可行解 int i = 0; for(; i < sub_size;) { if(right - _left < sub_size) break; // 窗口失效 if(!flag[*(sub + i)]) break; // 窗口失效 if(*(_left + i) != *(sub + i)) { --flag[*(_left + i)]; // 窗口内字符数更新 ++_left; i= 0; continue; // 缩小窗口，重新匹配 } ++i; } if(i == sub_size) return _left; // 查找成功 } return end; // 查找失败 } int main () { printf("%s\n", matchString("abccbaaabcbaabcacbacb", "acb")); return 0; }输出
acbacb问题
找到字符串中所有字⺟异位词？
⽆重复字符的最⻓⼦串？
创作不易，小小的支持一下吧！
